Submission #447973

#TimeUsernameProblemLanguageResultExecution timeMemory
447973zxcvbnmTraffic (CEOI11_tra)C++14
0 / 100
81 ms6272 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int nax = 6005; #define x first #define y second int n, m, a, b; vector<int> adj[nax]; vector<int> radj[nax]; vector<pair<int, int>> p; vector<int> from, to; bool vis_west[nax]; bool vis_east[nax]; void dfs1(int v) { vis_east[v] = true; for(int u : adj[v]) { if (!vis_east[u]) { dfs1(u); } } } void dfs2(int v) { vis_west[v] = true; for(int u : radj[v]) { if (!vis_west[u]) { dfs2(u); } } } int south[nax], north[nax]; bool vis[nax]; void dfs_north(int v, int par) { vis[v] = true; for(int u : adj[v]) { if (p[u].x == a) { north[par] = max(north[par], u); } if (!vis[u]) { dfs_north(u, par); } } } void dfs_south(int v, int par) { vis[v] = true; for(int u : adj[v]) { if (p[u].x == a) { south[par] = min(south[par], u); } if (!vis[u]) { dfs_south(u, par); } } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m >> a >> b; p.resize(n); for(int i = 0; i < n; i++) { cin >> p[i].x >> p[i].y; if (p[i].x == 0) { from.push_back(i); } else if (p[i].x == a) { to.push_back(i); } } for(int i = 0; i < m; i++) { int v1, v2, type; cin >> v1 >> v2 >> type; v1--, v2--; adj[v1].push_back(v2); radj[v2].push_back(v1); if (type == 2) { adj[v2].push_back(v1); radj[v1].push_back(v2); } } sort(from.begin(), from.end(), [&](const int& left, const int& right) { return p[left].y < p[right].y; }); sort(to.begin(), to.end(), [&](const int& left, const int& right) { return p[left].y < p[right].y; }); for(int i : from) { if (!vis_east[i]) { dfs1(i); } } vector<int> east; for(int i : to) { if (vis_east[i]) { east.push_back(i); } } for(int i : to) { if (!vis_west[i]) { dfs2(i); } } vector<int> west; for(int i : from) { if (vis_west[i]) { west.push_back(i); } } sort(east.begin(), east.end(), [&](const int& left, const int& right) { return p[left].y < p[right].y; }); sort(west.begin(), west.end(), [&](const int& left, const int& right) { return p[left].y < p[right].y; }); int sz = west.size(); for(int i = sz-1; i >= 0; i--) { if (i != sz-1) { south[west[i]] = south[west[i+1]]; } else { south[west[i]] = n; } dfs_south(west[i], west[i]); // cout << "SOUTH: " << west[i]+1 << " " << south[west[i]]+1 << "\n"; } fill(vis, vis+nax, false); for(int i = 0; i < sz; i++) { if (i != 0) { north[west[i]] = north[west[i-1]]; } else { north[west[i]] = 0; } dfs_north(west[i], west[i]); // cout << "WEST: " << west[i]+1 << " " << north[west[i]]+1 << "\n"; } vector<int> new_idx(n+1); int idx = 0; for(int i : east) { new_idx[i] = idx++; } idx = 0; vector<int> comp(n+1); for(int i : from) { comp[i] = idx++; // cout << east[i] << " " << new_idx[east[i]] << "\n"; } vector<int> ans((int) from.size(), 0); for(int i : west) { ans[comp[i]] = new_idx[north[i]] - new_idx[south[i]] + 1; } reverse(ans.begin(), ans.end()); for(int i : ans) { cout << i << "\n"; } return 0; }
#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...