Submission #774575

#TimeUsernameProblemLanguageResultExecution timeMemory
774575NK_Traffic (CEOI11_tra)C++17
100 / 100
522 ms50868 KiB
// Success consists of going from failure to failure without loss of enthusiasm #include <bits/stdc++.h> using namespace std; #define nl '\n' #define f first #define s second #define mp make_pair #define sz(x) int(x.size()) #define pb push_back using pi = pair<int, int>; template<class T> using V = vector<T>; const int INF = 1e9 + 10; int main() { cin.tie(0)->sync_with_stdio(0); int N, M, A, B; cin >> N >> M >> A >> B; V<pi> P(N); for(auto& x : P) cin >> x.f >> x.s; V<V<int>> adj(N); for(int i = 0; i < M; i++) { int u, v, d; cin >> u >> v >> d; --u, --v, --d; adj[u].pb(v); if (d) adj[v].pb(u); } V<int> low(N, INF), disc(N, 0), comp(N, -1), st, comps; // FIND SCCs int t = 0; function<int(int)> dfs = [&](int u) { st.pb(u); low[u] = disc[u] = ++t; for(const auto &v : adj[u]) { if (comp[v] == -1) low[u] = min(low[u], disc[v] ?: dfs(v)); } if (low[u] == disc[u]) { comps.pb(u); for(int v = -1; v != u; ) comp[v = st.back()] = u, st.pop_back(); } return low[u]; }; for(int i = 0; i < N; i++) if (!disc[i]) dfs(i); // SCCs V<V<int>> C(N); for(int i = 0; i < N; i++) { C[comp[i]].pb(i); } // WEST JUNCTIONS V<int> found(N); function<void(int)> see = [&](int u) { found[u] = 1; for(const auto &v : adj[u]) if (!found[v]) see(v); }; V<int> W; for(int i = 0; i < N; i++) { if (P[i].f == 0) { W.pb(i); see(i); } } sort(begin(W), end(W), [&](int x, int y) { return P[x].s > P[y].s; }); // EAST JUNCTIONS V<int> E; for(int i = 0; i < N; i++) if (found[i]) { if (P[i].f == A) E.pb(i); } sort(begin(E), end(E), [&](int x, int y) { return P[x].s > P[y].s; }); // FIND INTERVALS OF JUNCTIONS V<int> L(N, INF), R(N, -INF); for(int i = 0; i < sz(E); i++) { int e = E[i]; L[comp[e]] = min(L[comp[e]], i); R[comp[e]] = max(R[comp[e]], i); } for(const auto &c : comps) { for(const auto &u : C[c]) for(const auto &v : adj[u]) { int cv = comp[v]; L[c] = min(L[c], L[cv]); R[c] = max(R[c], R[cv]); } } for(auto u : W) cout << max(0, R[comp[u]] - L[comp[u]] + 1) << nl; 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...