fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. template<typename T>
  12. void maximize(T& a, const T& b) {
  13. 	if (a < b) a = b;  
  14. }
  15.  
  16. const int N = 1e3 + 5; 
  17.  
  18. // Xét đường đi P bất kì đi từ 1 đến n
  19. // Ta có P = e(i1), e(i2),..., e(ik) là các cạnh có trên đường đi
  20. // Khi đó f(P) = [lx, rx] = giao của tất cả các đoạn [l(i1), r(i1)], [l(i2), r(i2)],..., [l(ik), r(ik)]
  21. // Suy ra max{l(i)} <= lx <= rx <= min{r(i)}
  22. //        hay l(i) <= lx <= rx <= r(i) với mọi i (*)
  23. // Nhận xét: 
  24. // - lx sẽ chính là l(i) nào đấy, nên thay vì duyệt lx từ 1 -> 1e6 thì ta chỉ duyệt trong các l(i) 
  25. // - Khi đã chốt lx, với rx càng lớn thì càng khó để đi được từ 1 đến n, do đó ta có thể tìm kiếm nhị phân rx              
  26. // - Để check [lx, rx] có thoả mãn hay không thì đơn giản là ta dfs/bfs từ 1 xem có thể đi được đến n hay không (xem (*))
  27. // Độ phức tạp: O(m * log2(1e6) * (n + m))
  28. struct EdgeInfo {
  29. 	int v, l, r; 
  30. }; 
  31.  
  32. int n, m;  
  33. vector<EdgeInfo> adj[N];  
  34.  
  35. bool vis[N];  
  36.  
  37. bool bfs(int s, int lx, int rx) {
  38. 	for (int u = 1; u <= n; u++) vis[u] = false;  
  39.  
  40. 	queue<int> q;  
  41. 	vis[s] = true;  
  42. 	q.push(s);  
  43.  
  44. 	while (!q.empty()) {
  45. 		int u = q.front(); q.pop();  
  46.  
  47. 		if (u == n) return true;   
  48.  
  49. 		for (auto e : adj[u]) {
  50. 			int v = e.v, l = e.l, r = e.r;  
  51. 			if ((l <= lx && rx <= r) && !vis[v]) {
  52. 				vis[v] = true; 
  53. 				q.push(v); 
  54. 			}
  55. 		}
  56. 	}
  57.  
  58. 	return false; 
  59. }
  60.  
  61. bool check(int lx, int mid) {
  62. 	return bfs(1, lx, mid);  
  63. }
  64.  
  65. int findR(int lx) {
  66. 	int lo = lx, hi = 1e6, ans = -1;  
  67. 	while (lo <= hi) {
  68. 		int mid = (lo + hi) >> 1;  
  69. 		if (check(lx, mid)) {
  70. 			ans = mid;   
  71. 			lo = mid + 1; 
  72. 		}
  73. 		else {
  74. 			hi = mid - 1; 
  75. 		}
  76. 	}
  77. 	return ans; 
  78. }
  79.  
  80. int main() {
  81. 	ios::sync_with_stdio(false); 
  82. 	cin.tie(nullptr); 	
  83. 	cin >> n >> m; 
  84.  
  85. 	vector<int> ls;  
  86. 	for (int i = 0; i < m; i++) {
  87. 		int u, v, l, r; 
  88. 		cin >> u >> v >> l >> r; 
  89. 		adj[u].push_back({v, l, r});   
  90. 		adj[v].push_back({u, l, r}); 
  91. 		ls.push_back(l); 
  92. 	}
  93.  
  94. 	int ans = 0;  
  95. 	for (int lx : ls) {
  96. 		int rx = findR(lx);  
  97. 		if (rx == -1) continue;  
  98. 		maximize(ans, rx - lx + 1);  
  99. 	}
  100.  
  101. 	if (ans == 0) {
  102. 		cout << "Nice work, Dima!" << '\n'; 
  103. 	}
  104. 	else {
  105. 		cout << ans << '\n'; 
  106. 	}
  107. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
4 4
1 2 1 10
2 4 3 5
1 3 1 5
2 4 2 7
stdout
copy 
6
https://ideone.com/hODSMp
language:
C++14 (gcc 8.3)
created:
220 days ago
visibility:
secret

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!