Submission #958282

#TimeUsernameProblemLanguageResultExecution timeMemory
958282LithaniumTraffic (CEOI11_tra)C++17
100 / 100
1335 ms69312 KiB
#include <bits/stdc++.h> using namespace std; vector<pair<int, int>> leftSide, rightSide; vector<int> adj[300005], rev[300005]; int loc[300005][2], pos[300005], temp, a, b; bool seen[300005], dead[300005]; int ans[300005][2]; //North South void dfs(int n) { seen[n] = 1; for (int i:adj[n]) if (!seen[i]) dfs(i); } void dfs2(int n) { seen[n] = 1; for (int i:rev[n]) if (!seen[i]) dfs2(i); } void solve(int n, bool north) { seen[n] = 1; if (loc[n][0] == a) { if (!north) temp = max(temp, pos[n]); else temp = min(temp, pos[n]); } for (int i:adj[n]) if (!seen[i]) solve(i, north); } int main() { int n, m; cin >> n >> m >> a >> b; for (int i = 1; i <= n; i ++) { cin >> loc[i][0] >> loc[i][1]; if (loc[i][0] == 0) { leftSide.push_back({loc[i][1], i}); } else if (loc[i][0] == a) { rightSide.push_back({loc[i][1], i}); } } while (m --) { int a1, b1, c1; cin >> a1 >> b1 >> c1; adj[a1].push_back(b1); rev[b1].push_back(a1); if (c1 == 2) {adj[b1].push_back(a1); rev[a1].push_back(b1);} } sort(leftSide.begin(), leftSide.end()); sort(rightSide.begin(), rightSide.end()); for (auto[x, y]:leftSide) if (!seen[y]) dfs(y); for (int i = 1; i <= n; i ++) if (loc[i][0] == a and !seen[i]) dead[i] = 1; memset(seen, 0, sizeof(seen)); for (auto[x, y]:rightSide) if (!seen[y]) dfs2(y); //for (int i = 1; i <= n; i ++) cout << seen[i] << " "; for (int i = 0; i <= n; i ++) if (loc[i][0] == 0 and !seen[i]) dead[i] = 1; int ptr = 1; for (int i = 0; i < rightSide.size(); i ++) { auto[x, y] = rightSide[i]; if (!dead[y]) { pos[y] = ptr; ptr ++; } } // South Side memset(seen, 0, sizeof(seen)); for (auto[x, y]:leftSide) if (!dead[y]) { solve(y, 0); ans[y][1] = temp; } // North Side memset(seen, 0, sizeof(seen)); temp = 1e9; reverse(leftSide.begin(), leftSide.end()); for (auto[x, y]:leftSide) if (!dead[y]) { solve(y, 1); ans[y][0] = temp; } //for (int i = 1; i <= n; i ++) cout << dead[i] << " "; //cout << "\n"; for (auto[x, y]:leftSide) { if (dead[y]) cout << "0\n"; else cout << ans[y][1] - ans[y][0] + 1 << "\n"; } }

Compilation message (stderr)

tra.cpp: In function 'int main()':
tra.cpp:56:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for (int i = 0; i < rightSide.size(); i ++) {
      |                     ~~^~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...