Submission #449359

#TimeUsernameProblemLanguageResultExecution timeMemory
449359ritul_kr_singhTraffic (CEOI11_tra)C++17
100 / 100
784 ms49088 KiB
#include <bits/stdc++.h> using namespace std; #define sp << ' ' << #define nl << '\n' const int LIM = 3e5+1; int n, m, A, B, dfsNum[LIM], id[LIM], L[LIM], R[LIM], pre[LIM], dfsTimer, st[LIM], stP; vector<int> g[LIM], h[LIM]; array<int, 3> p[LIM]; int dfs(int u){ int low = dfsNum[u] = ++dfsTimer; st[stP++] = u; for(int &v : g[u]) if(id[v] < 0) low = min(low, dfsNum[v] ? : dfs(v)); if(low == dfsNum[u]){ for(int c=n; c!=u; ){ id[c = st[--stP]] = u; for(int &v : g[c]){ L[u] = min(L[u], L[id[v] < 0 || id[v] == u ? v : id[v]]); R[u] = max(R[u], R[id[v] < 0 || id[v] == u ? v : id[v]]); } } } return low; } signed main(){ cin.tie(0)->sync_with_stdio(0); cin >> n >> m >> A >> B; fill(L, L+n, n+1); for(int i=0; i<n; ++i){ auto &[x, y, j] = p[i]; cin >> x >> y; j = i; } for(int i=0; i<m; ++i){ int u, v, w; cin >> u >> v >> w; --u, --v; g[u].push_back(v); if(w > 1) g[v].push_back(u); } sort(p, p+n, [&](auto &x, auto &y){ return x[1] < y[1]; }); for(int i=0; i<n; ++i){ auto &[x, y, j] = p[i]; if(x == A) L[j] = R[j] = i+1; } fill(id, id+n, -1); for(int u=0; u<n; ++u) if(!p[u][0] && !dfsNum[p[u][2]]) dfs(p[u][2]); for(int i=0; i<n; ++i){ if(dfsNum[p[i][2]] && p[i][0] == A) ++pre[i+1]; pre[i+1] += pre[i]; } for(int i=n; --i>=0; ){ int j = id[p[i][2]]; if(!p[i][0]) cout << (R[j] ? pre[R[j]] - pre[L[j]-1] : 0) nl; } }
#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...