fork download
copy 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cstring>
  4. #include <vector>
  5. #include <map>
  6. using namespace std;
  7. const int MAX = 50005;
  8. vector<int> edges[MAX];
  9. int from[MAX], to[MAX], color[MAX], cost[MAX];
  10. bool cmp(int x, int y)
  11. {
  12. 	return (color[x] < color[y]);
  13. }
  14. vector<pair<int, int> > bads;
  15. vector<int> adj[8 * MAX], tmp[8 * MAX];
  16. int n, m, sz;
  17. void init()
  18. {
  19. 	for (int i = 0; i < 8 * MAX; i++)
  20. 		adj[i].clear();
  21. 	for (int i = 0; i < (int)bads.size(); i++)
  22. 	{
  23. 		int id1 = bads[i].first, id2 = bads[i].second;
  24. 		adj[2 * id1].push_back(2 * id2 + 1);
  25. 		adj[2 * id2].push_back(2 * id1 + 1);
  26. 	}
  27. 	sz = m;
  28. 	for (int v = 0; v < n; v++)
  29. 		if (!edges[v].empty())
  30. 		{
  31. 			int last = edges[v][0];
  32. 			for (int i = 1; i < (int)edges[v].size(); i++)
  33. 			{
  34. 				int id = edges[v][i];
  35. 				adj[2 * last + 1].push_back(2 * id);
  36. 				adj[2 * id + 1].push_back(2 * last);
  37. 				adj[2 * id + 1].push_back(2 * sz + 1);
  38. 				adj[2 * sz].push_back(2 * id);
  39. 				adj[2 * last + 1].push_back(2 * sz + 1);
  40. 				adj[2 * sz].push_back(2 * last);
  41. 				last = sz++;
  42. 			}
  43. 		}
  44. }
  45. vector<int> tp;
  46. bool mark[8 * MAX];
  47. void dfs(int v)
  48. {
  49. 	mark[v] = true;
  50. 	for (int i = 0; i < (int)adj[v].size(); i++)
  51. 	{
  52. 		int u = adj[v][i];
  53. 		if (!mark[u])
  54. 			dfs(u);
  55. 	}
  56. 	tp.push_back(v);
  57. }
  58. int cc[8 * MAX];
  59. void sfd(int v, int col)
  60. {
  61. 	mark[v] = true;
  62. 	cc[v] = col;
  63. 	for (int i = 0; i < (int)adj[v].size(); i++)
  64. 	{
  65. 		int u = adj[v][i];
  66. 		if (!mark[u])
  67. 			sfd(u, col);
  68. 	}
  69. }
  70. vector<int> ans;
  71. bool check(int lim)
  72. {
  73. 	init();
  74. 	sz *= 2;
  75. 	for (int i = 0; i < m; i++)
  76. 		if (cost[i] > lim)
  77. 			adj[2 * i + 1].push_back(2 * i);
  78. 	memset(mark, false, sizeof(mark));
  79. 	tp.clear();
  80. 	for (int i = 0; i < sz; i++)
  81. 		if (!mark[i])
  82. 			dfs(i);
  83. 	reverse(tp.begin(), tp.end());
  84. 	for (int i = 0; i < sz; i++)
  85. 		tmp[i].clear();
  86. 	for (int v = 0; v < sz; v++)
  87. 		for (int i = 0; i < (int)adj[v].size(); i++)
  88. 			tmp[adj[v][i]].push_back(v);
  89. 	for (int i = 0; i < sz; i++)
  90. 		adj[i] = tmp[i];
  91. 	int cnt = 0;
  92. 	memset(mark, false, sizeof(mark));
  93. 	for (int i = 0; i < (int)tp.size(); i++)
  94. 		if (!mark[tp[i]])
  95. 			sfd(tp[i], cnt++);
  96. 	ans.clear();
  97. 	for (int i = 0; i < sz / 2; i++)
  98. 	{
  99. 		if (cc[2 * i] == cc[2 * i + 1])
  100. 			return false;
  101. 		if (i < m && cc[2 * i] < cc[2 * i + 1])
  102. 			ans.push_back(i);
  103. 	}
  104. 	return true;
  105. }
  106. int main()
  107. {
  108. 	ios::sync_with_stdio(false);
  109. 	cin >> n >> m;
  110. 	vector<int> vals;
  111. 	vals.push_back(0);
  112. 	for (int i = 0; i < m; i++)
  113. 	{
  114. 		cin >> from[i] >> to[i] >> color[i] >> cost[i];
  115. 		vals.push_back(cost[i]);
  116. 		from[i]--;
  117. 		to[i]--;
  118. 		edges[from[i]].push_back(i);
  119. 		edges[to[i]].push_back(i);
  120. 	}
  121. 	for (int v = 0; v < n; v++)
  122. 	{
  123. 		sort(edges[v].begin(), edges[v].end(), cmp);
  124. 		int cnt = 0;
  125. 		for (int i = 0; i < (int)edges[v].size(); i++)
  126. 		{
  127. 			int j = i + 1;
  128. 			while (j < (int)edges[v].size() && color[edges[v][j - 1]] == color[edges[v][j]])
  129. 				j++;
  130. 			if (j - i > 2)
  131. 			{
  132. 				cout << "No\n";
  133. 				return 0;
  134. 			}
  135. 			if (j - i == 2)
  136. 			{
  137. 				cnt++;
  138. 				if (cnt == 2)
  139. 				{
  140. 					cout << "No\n";
  141. 					return 0;
  142. 				}
  143. 				bads.push_back(make_pair(edges[v][i], edges[v][i + 1]));
  144. 				i++;
  145. 			}
  146. 		}
  147. 	}
  148. 	sort(vals.begin(), vals.end());
  149. 	vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
  150. 	int l = -1, r = (int)vals.size();
  151. 	while (r - l > 1)
  152. 	{
  153. 		int mid = (l + r) / 2;
  154. 		if (check(vals[mid]))
  155. 			r = mid;
  156. 		else
  157. 			l = mid;
  158. 	}
  159. 	if (r == (int)vals.size())
  160. 	{
  161. 		cout << "No\n";
  162. 		return 0;
  163. 	}
  164. 	check(vals[r]);
  165. 	cout << "Yes\n";
  166. 	cout << vals[r] << " " << ans.size() << "\n";
  167. 	for (int i = 0; i < (int)ans.size(); i++)
  168. 		cout << ans[i] + 1 << " ";
  169. 	cout << "\n";
  170. 	return 0;
  171. }
  172.  
Success #stdin #stdout 0.01s 16160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Yes
0 0
https://ideone.com/LvFDOX
language:
C++14 (gcc 8.3)
created:
9 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!