fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int maxN=1e6;
  4. int card[maxN][2], num[maxN*2], p[maxN*2];
  5. int vn[maxN*2], en[maxN*2], mv[maxN*2];//vertix edge minNum
  6. long sv[maxN*2];
  7.  
  8.  
  9. int findP(int x){
  10. 	return (x==p[x])?x:p[x]=findP(p[x]);
  11. }
  12.  
  13. int main(){
  14. 	ios::sync_with_stdio(0);
  15. 	cin.tie(0); cout.tie(0);
  16. 	int N;
  17. 	cin>>N;
  18. 	for(int i=0; i<N; i++){
  19. 		cin>>card[i][0]>>card[i][1];
  20. 		num[i]=card[i][0];
  21. 		num[i+N]=card[i][1];
  22. 	}
  23. 	//離散化
  24. 	sort(num,num+N*2);
  25. 	int uN=unique(num,num+N*2)-num;
  26. 	//DSU
  27. 	for(int i=0; i<uN; i++){
  28. 		p[i]=i, vn[i]=1, en[i]=0;
  29. 		sv[i]=mv[i]=num[i];
  30. 	}
  31. 	for(int i=0; i<N; i++){
  32. 		int n1=lower_bound(num,num+uN,card[i][0])-num;
  33. 		int n2=lower_bound(num,num+uN,card[i][1])-num;
  34. 		int p1=findP(n1), p2=findP(n2);
  35. 		if(p1!=p2){
  36. 			p[p2]=p1;
  37. 			vn[p1]+=vn[p2];
  38. 			en[p1]+=en[p2]+1;
  39. 			mv[p1]=min(mv[p1],mv[p2]);
  40. 			sv[p1]+=sv[p2];
  41. 		}else en[p1]++;
  42. 	}
  43. 	long ans=0;
  44. 	for(int i=0; i<uN; i++){
  45. 		if(i!=findP(i)) continue;
  46. 		ans+=sv[i]-(en[i]>=vn[i]?0:mv[i]);
  47. 	}cout<<ans;
  48. }
Success #stdin #stdout 0.01s 15788KB
comments (?)
stdin
copy 
3
1 2
1 2
1 2
stdout
copy 
3
https://ideone.com/clZTKe
e370. 翻牌
language:
C++14 (clang 8.0)
created:
15 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!