fork download
  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
stdin
Standard input is empty
stdout
Yes
0 0