fork download
copy 
  1. /*
  2. Saurabh Joshi
  3. IIIT Jabalpur
  4. */
  5. #include<bits/stdc++.h>
  6. #define LL long long int
  7. #define M 1000000007
  8. #define reset(a) memset(a,0,sizeof(a))
  9. #define rep(i,j,k) for(i=j;i<=k;++i)
  10. #define per(i,j,k) for(i=j;i>=k;--i)
  11. #define print(a,start,end) for(i=start;i<=end;++i) cout<<a[i];
  12. #define endl "\n"
  13. #define eps 0.00000001
  14. #define check(a , b , c) assert(a >= b && a <= c)
  15. LL pow(LL a,LL b,LL m){LL x=1,y=a;while(b > 0){if(b%2 == 1){x=(x*y);if(x>m) x%=m;}y = (y*y);if(y>m) y%=m;b /= 2;}return x%m;}
  16. LL gcd(LL a,LL b){if(b==0) return a; else return gcd(b,a%b);}
  17. LL gen(LL start,LL end){LL diff = end-start;LL temp = rand()%start;return temp+diff;}
  18. using namespace std;
  19. int u[200001];
  20. int v[200001];
  21. int w[200001];
  22. vector<int> graph[200001];
  23. bool visit[200001];
  24. int sz = 0;
  25. int eg = 0;
  26. int deg[200001];
  27. vector<pair<int,int> > watered;
  28. vector<pair<int,int> > dry;
  29. void dfs(int node)
  30. 	{
  31. 		sz++;
  32. 		visit[node] = 1;
  33. 		eg += deg[node];
  34. 		for(int i: graph[node])
  35. 			{
  36. 				if(visit[i] == 0)
  37. 					{
  38. 						visit[i] = 1;
  39. 						dfs(i);
  40. 					}
  41. 			}
  42. 	}
  43. int main()
  44.     {
  45.         ios_base::sync_with_stdio(0);
  46. 		int n , m , k;
  47. 		cin >> n >> m >> k;
  48. 		for(int i = 0; i < m; i++)
  49. 			{
  50. 				cin >> u[i] >> v[i];
  51. 				graph[u[i]].push_back(v[i]);
  52. 				graph[v[i]].push_back(u[i]);
  53. 				++deg[u[i]];
  54. 				++deg[v[i]];
  55. 			}
  56. 		for(int i = 0; i < k; i++)
  57. 			cin >> w[i];
  58. 		LL ans1 = 0 , ans2 = 0;
  59. 		LL maxsz = 0;
  60. 		for(int i = 0; i < k; i++)
  61. 			{
  62. 				sz = 0;
  63. 				eg = 0;
  64. 				if(visit[w[i]] == 1)
  65. 					continue;
  66. 				dfs(w[i]);
  67. 				maxsz = max(maxsz , (LL)sz);
  68. 				eg /= 2;
  69. 				watered.push_back(make_pair(sz , eg));
  70. 				ans1 += (sz * (sz - 1)) / 2 - eg;
  71. 			}
  72. 		for(int i = 1; i <= n; i++)
  73. 			{
  74. 				if(visit[i] == 0)
  75. 					{
  76. 						sz = 0;
  77. 						eg = 0;
  78. 						dfs(i);
  79. 						eg /= 2;
  80. 						dry.push_back(make_pair(sz , eg));
  81. 						ans1 += (sz * (sz - 1)) / 2 - eg;
  82. 					}
  83. 			}
  84. 		sort(watered.begin() , watered.end());
  85.  
  86. 		LL pre = 0 , cur = 0;
  87. 		for(int i = 0; i < dry.size(); i++)
  88. 			{
  89. 				ans2 = ans2 + pre * dry[i].first;
  90. 				ans1 += pre * dry[i].first;
  91. 				pre += dry[i].first;
  92. 			}
  93.  
  94. 		ans2 += pre * maxsz;
  95. 		ans1 += pre * maxsz;
  96. 		cout << ans1 << " " << ans2;
  97.  
  98. 	}
  99.  
Success #stdin #stdout 0.01s 9816KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0
https://ideone.com/ObgBMP
language:
C++ (gcc 8.3)
created:
2 years 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!