fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. #define fi first
  9. #define se second
  10. #define mp make_pair
  11. #define pb push_back
  12. #define fbo find_by_order
  13. #define ook order_of_key
  14.  
  15. typedef long long ll;
  16. typedef pair<int,int> ii;
  17. typedef vector<int> vi;
  18. typedef long double ld; 
  19. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
  20. typedef set<int>::iterator sit;
  21. typedef map<int,int>::iterator mit;
  22. typedef vector<int>::iterator vit;
  23.  
  24. vector<pair<ii,int> > edges;
  25. vector<ii> adj[100001];
  26. int C;
  27. set<pair<ii,int> > s;
  28. const int MX = 100000;
  29.  
  30. ll hsh(int a, int b)
  31. {	
  32. 	return (ll(a)*1000001LL + ll(b));
  33. }
  34.  
  35. unordered_map<ll,int> ma;
  36.  
  37. void ins(int a, int b, int c)
  38. {
  39. 	if(s.size() > MX) return ;
  40. 	//int x[3];
  41. 	//x[0]=a; x[1]=b; x[2]=c;
  42. 	//sort(x,x+3);
  43. 	//s.insert(mp(mp(x[0],x[1]),x[2]));
  44. 	if(a>b) swap(a,b);
  45. 	if(a>c) swap(a,c);
  46. 	if(b>c) swap(b,c);
  47. 	s.insert(mp(mp(a,b),c));
  48. }
  49.  
  50. int n, m;
  51.  
  52. bool heavy(int u)
  53. {
  54. 	if(adj[u].size() >= C) return true;
  55. 	return false;
  56. }
  57.  
  58. ll ansheavy;
  59. ll anslight;
  60.  
  61. void processheavy(int x)
  62. {
  63. 	for(int i = 0; i < m; i++)
  64. 	{
  65. 		int heavycnt = 1;
  66. 		int u = edges[i].fi.fi; int v = edges[i].fi.se; int c = edges[i].se;
  67. 		if(u==x||v==x) continue;
  68. 		if(heavy(u)) heavycnt++;
  69. 		if(heavy(v)) heavycnt++;
  70. 		int c1 = ma[hsh(u,x)];
  71. 		int c2 = ma[hsh(v,x)];
  72. 		if(c1==0||c2==0) continue;
  73. 		if(c!=c1&&c1!=c2&&c!=c2)
  74. 		{
  75. 			ins(x,u,v);
  76. 			if(heavycnt==3)
  77. 			{
  78. 				ansheavy+=2;
  79. 			}
  80. 			else if(heavycnt==2)
  81. 			{
  82. 				ansheavy+=3;
  83. 			}
  84. 			else
  85. 			{
  86. 				ansheavy+=6;
  87. 			}
  88. 		}
  89. 	}	
  90. }
  91.  
  92. void processlight(int u, int v, int c)
  93. {
  94. 	for(int i = 0; i < adj[u].size(); i++)
  95. 	{
  96. 		int w = adj[u][i].fi; int c1 = adj[u][i].se;
  97. 		if(heavy(w)) continue;
  98. 		int c2 = ma[hsh(v,w)];
  99. 		if(c2==0) continue;
  100. 		if(c1!=c2&&c2!=c&&c!=c1)
  101. 		{
  102. 			anslight++;
  103. 			ins(u,v,w);
  104. 		}	
  105. 	}
  106. }
  107.  
  108. int main()
  109. {
  110. 	ios_base::sync_with_stdio(0); cin.tie(0);
  111. 	int k;
  112. 	cin>>n>>m>>k;
  113. 	C = 450;
  114. 	for(int i = 0; i < m; i++)
  115. 	{
  116. 		int u, v, c;
  117. 		cin>>u>>v>>c;
  118. 		u--; v--;
  119. 		ma[hsh(u,v)] = c;
  120. 		ma[hsh(v,u)] = c;
  121. 		adj[u].pb(mp(v,c));
  122. 		adj[v].pb(mp(u,c));
  123. 		edges.pb(mp(mp(u,v),c));
  124. 	}
  125. 	for(int i = 0; i < n; i++)
  126. 	{
  127. 		if(heavy(i))
  128. 		{
  129. 			processheavy(i);
  130. 		}
  131. 	}
  132. 	for(int i = 0; i < m; i++)
  133. 	{
  134. 		int u = edges[i].fi.fi; int v = edges[i].fi.se; int c = edges[i].se;
  135. 		if(heavy(u)||heavy(v)) continue;
  136. 		processlight(u,v,c);
  137. 	}
  138. 	ansheavy/=6;
  139. 	anslight/=3;
  140. 	ll ans = ansheavy + anslight;
  141. 	cout<<ans<<'\n';
  142. 	if(ans <= MX)
  143. 	{
  144. 		for(set<pair<ii,int> >::iterator it = s.begin(); it != s.end(); it++)
  145. 		{
  146. 			cout << (*it).fi.fi+1 << ' ' << (*it).fi.se + 1 << ' ' << (*it).se + 1 << '\n';
  147. 		}
  148. 	}
  149. }
  150.  
Success #stdin #stdout 0s 18416KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/5d7NrS
language:
C++14 (gcc 8.3)
created:
7 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!