Submission #654273

#TimeUsernameProblemLanguageResultExecution timeMemory
654273fabijan_cikacTraffic (CEOI11_tra)C++17
0 / 100
999 ms76740 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define pp pair<int, int> #define F first #define S second struct point{ int x, y, ix; }; const int N = 3 * 1e5 + 100; int n, m, A, B; vector<point> pt; vector<int> g[N], tg[N], graph[N], order; int new_idx[N], root[N], used[N], l[N], r[N]; bool cmp(point x, point y){ if (x.x != y.x) return (x.x < y.x); return (x.y > y.y); } void dfs1(int x){ used[x] = 1; for (int y: g[x]){ if (!used[y]) dfs1(y); } order.pb(x); } int cnt = 0; void dfs2(int x){ used[x] = 1; for (int y: tg[x]){ if (!used[y]) dfs2(y); } root[x] = cnt; if (pt[x].x == A){ l[cnt] = min(l[cnt], x); r[cnt] = max(r[cnt], x); } } void dfs3(int x){ used[x] = 1; for (int y: graph[x]){ if (!used[y]) dfs3(y); l[x] = min(l[x], l[y]); r[x] = max(r[x], r[y]); } //cout << ": " << x << ' ' << l[x] << ' ' << r[x] << endl; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m >> A >> B; pt.resize(n); int k = 1; for (int i = 0; i < n; ++i){ cin >> pt[i].x >> pt[i].y; pt[i].ix = i; } sort(pt.begin(), pt.end(), cmp); for (auto i = 0; i < n; ++i){ new_idx[pt[i].ix] = i; l[i] = N; r[i] = -1; } for (int i = 0; i < m; ++i){ int u, v, k; cin >> u >> v >> k; --u; --v; u = new_idx[u]; v = new_idx[v]; g[u].pb(v); tg[v].pb(u); if (k == 2){ g[v].pb(u); tg[u].pb(v); } } while (k < n && pt[k].x == 0) ++k; for (int i = 0; i < k; ++i){ if (!used[i]) dfs1(i); } memset(used, 0, sizeof(used)); /*cout << "-----------------------------" << endl; for (auto x: pt) cout << x.x << ' ' << x.y << ' ' << x.ix << endl; for (int x: order) cout << x << ' '; cout << endl;*/ reverse(order.begin(), order.end()); for (int x: order){ if (!used[x]){ dfs2(x); ++cnt; } } /*for (int i = 0; i < n; ++i) cout << root[i] << ' '; cout << endl;*/ for (int i = 0; i < n; ++i){ for (int x: g[i]) graph[root[i]].pb(root[x]); } memset(used, 0, sizeof(used)); for (int i = 0; i < cnt; ++i){ if (!used[i]) dfs3(i); } /*for (int i = 0; i < n; ++i) cout << l[i] << ' ' << r[i] << endl;*/ for (int i = 0; i < k; ++i){ int x = root[i]; if (l[x] == N) cout << 0; else cout << (r[x] - l[x] + 1); cout << '\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...