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. using namespace __gnu_pbds;
  5. using namespace std;
  6. #define Foreach(i, c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
  7. #define For(i,a,b) for(int (i)=(a);(i) < (b); ++(i))
  8. #define rof(i,a,b) for(int (i)=(a);(i) > (b); --(i))
  9. #define rep(i, c) for(auto &(i) : (c))
  10. #define x first
  11. #define y second
  12. #define pb push_back
  13. #define PB pop_back()
  14. #define iOS ios_base::sync_with_stdio(false)
  15. #define sqr(a) (((a) * (a)))
  16. #define all(a) a.begin() , a.end()
  17. #define error(x) cerr << #x << " = " << (x) <<endl
  18. #define Error(a,b) cerr<<"( "<<#a<<" , "<<#b<<" ) = ( "<<(a)<<" , "<<(b)<<" )\n";
  19. #define errop(a) cerr<<#a<<" = ( "<<((a).x)<<" , "<<((a).y)<<" )\n";
  20. #define coud(a,b) cout<<fixed << setprecision((b)) << (a)
  21. #define L(x) ((x)<<1)
  22. #define R(x) (((x)<<1)+1)
  23. #define umap unordered_map
  24. #define double long double
  25. typedef long long ll;
  26. typedef pair<int,int>pii;
  27. typedef vector<int> vi;
  28. typedef complex<double> point;
  29. template <typename T> using os =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  30. template <class T>  inline void smax(T &x,T y){ x = max((x), (y));}
  31. template <class T>  inline void smin(T &x,T y){ x = min((x), (y));}
  32. const int maxn = 5e4 + 10, maxN = 6 * maxn;
  33. int n, m, comp[maxN];
  34. vi adj[maxN], adl[maxN];
  35. bool mark[maxN];
  36. struct edge{
  37. 	int v, u, c, t;
  38. }e[maxn];
  39. vi ed[maxn];
  40. inline int neg(int x){
  41. 	return x ^ 1;
  42. }
  43. inline void add_edge(int v, int u){
  44. 	adj[v].pb(u);
  45. 	adl[u].pb(v);
  46. }
  47. inline void add_clause(int v, int u){
  48. 	add_edge(neg(v), u);
  49. 	add_edge(neg(u), v);
  50. }
  51. int sz[maxN], SZ[maxN];
  52. stack <int> s;
  53. inline void dfs(int v){
  54. 	mark[v] = true;
  55. 	rep(u, adj[v])	if(!mark[u])
  56. 		dfs(u);
  57. 	s.push(v);
  58. }
  59. bool flag = true;
  60. inline void dfs(int v, int c){
  61. 	comp[v] = c;
  62. 	if(comp[v] == comp[neg(v)]){
  63. 		flag = false;
  64. 		return ;
  65. 	}
  66. 	rep(u, adl[v])	if(!comp[u]){
  67. 		dfs(u, c);
  68. 		if(!flag)	return ;
  69. 	}
  70. }
  71. int nex;
  72. inline bool check(int T){
  73. 	flag = true;
  74. 	For(i,0,nex){
  75. 		mark[i] = false;
  76. 		adj[i].resize(sz[i]);
  77. 		adl[i].resize(SZ[i]);
  78. 		comp[i] = 0;
  79. 	}
  80. 	while(!s.empty())	s.pop();
  81. 	For(i,0,m)	if(e[i].t > T)
  82. 		add_edge(L(i), R(i));
  83. 	For(i,0,nex)
  84. 		if(!mark[i])
  85. 			dfs(i);
  86. 	int cnt = 1;
  87. 	while(!s.empty()){
  88. 		int v = s.top();
  89. 		s.pop();
  90. 		if(comp[v])	continue;
  91. 		dfs(v, cnt ++);
  92. 		if(!flag)	return false;
  93. 	}
  94. 	return flag;
  95. }
  96. vi ts = {0};
  97. int main(){
  98. 	scanf("%d %d", &n, &m);
  99. 	For(i,0,m){
  100. 		scanf("%d %d %d %d", &e[i].v, &e[i].u, &e[i].c, &e[i].t);
  101. 		-- e[i].v;
  102. 		-- e[i].u;
  103. 		ed[e[i].v].pb(i);
  104. 		ed[e[i].u].pb(i);
  105. 		ts.pb(e[i].t);
  106. 	}
  107. 	nex = L(m);
  108. 	For(i,0,n){
  109. 		sort(all(ed[i]), [](const int &x, const int &y){return e[x].c < e[y].c;});
  110. 		int cnt = 0;
  111. 		int prv;
  112. 		if(!ed[i].empty()){
  113. 			prv = nex;
  114. 			nex += 2;
  115. 			add_clause(R(ed[i][0]), prv);
  116. 		}
  117. 		For(j,1,ed[i].size()){
  118. 			int x = ed[i][j-1], y = ed[i][j];
  119. 			int cur = nex;
  120. 			nex += 2;
  121. 			if(e[x].c == e[y].c){
  122. 				++ cnt;
  123. 				if(cnt >  1){
  124. 					puts("No");
  125. 					return 0;
  126. 				}
  127. 				add_clause(L(x), L(y));
  128. 			}
  129. 			add_clause(R(y), cur);
  130. 			add_clause(neg(prv), cur);
  131. 			add_clause(neg(prv), R(y));
  132. 			prv = cur;
  133. 		}
  134. 	}
  135. 	For(i,0,maxN)
  136. 		sz[i] = adj[i].size(),SZ[i] = adl[i].size();
  137. 	sort(all(ts));
  138. 	ts.resize(unique(all(ts)) - ts.begin());
  139. 	int lo = 0, hi = ts.size() - 1;
  140. 	while(lo < hi){
  141. 		int mid = (lo + hi)/2;
  142. 		if(check(ts[mid]))
  143. 			hi = mid;
  144. 		else
  145. 			lo = mid + 1;
  146. 	}
  147. 	if(lo >= (int)ts.size() or !check(ts[lo])){
  148. 		puts("No");
  149. 		return 0;
  150. 	}
  151. 	puts("Yes");
  152. 	fill(mark, mark + nex, false);
  153. 	int T = ts[lo];
  154. 	For(i,0,nex){
  155. 		int v = comp[i], u = comp[neg(i)];
  156. 		mark[min(v, u)] = false;
  157. 		mark[max(v, u)] = true;
  158. 	}
  159. 	vi ans;
  160. 	For(i,0,m)
  161. 		if(mark[comp[L(i)]])
  162. 			ans.pb(i + 1);
  163. 	int K = ans.size();
  164. 	printf("%d %d\n", T, K);
  165. 	int cnt = 0;
  166. 	rep(i, ans){
  167. 		printf("%d", i);
  168. 		++ cnt;
  169. 		if(cnt == K)
  170. 			puts("");
  171. 		else
  172. 			printf(" ");
  173. 	}
  174. 	return 0;
  175. }
Success #stdin #stdout 0s 15640KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Yes
0 0
https://ideone.com/KGepK0
language:
C++14 (gcc 8.3)
created:
8 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!