Submission #672699

#TimeUsernameProblemLanguageResultExecution timeMemory
672699haxormanTraffic (CEOI11_tra)C++14
8 / 100
5065 ms50732 KiB
#include <bits/stdc++.h> using namespace std; const int mxN = 3e5 + 7; int n, m, A, B, vis[mxN], vis_cnt = 1, dp[mxN], dsu[mxN], east[mxN], p[mxN]; bool st[mxN]; vector<pair<int,int>> west; set<int> graph[mxN]; int find(int x) { return dsu[x] == x ? x : dsu[x] = find(dsu[x]); } bool unite(int x, int y) { x = find(x), y = find(y); if (x == y) { return false; } if (graph[x].size() < graph[y].size()) { swap(x, y); } graph[x].insert(graph[y].begin(), graph[y].end()); east[x] += east[y]; dsu[y] = x; return true; } void findCycles(int u, int prev) { if (st[u]) { while (prev != u) { unite(u, prev); prev = p[prev]; } return; } st[u] = true; p[u] = prev; vis[u] = vis_cnt; for (auto v : graph[u]) { findCycles(find(v), u); } st[u] = false; } int dfs(int u) { if (vis[u] == vis_cnt) { return 0; } if (dp[u] != -1) { return dp[u]; } vis[u] = vis_cnt; dp[u] = east[u]; for (auto v : graph[u]) { dp[u] += dfs(find(v)); } return dp[u]; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m >> A >> B; map<pair<int,int>,int> pos; for (int i = 1; i <= n; ++i) { int x, y; cin >> x >> y; pos[{x, y}] = i; if (!x) { west.push_back({x, y}); } else if (x == A) { east[i] = 1; } } for (int i = 1; i <= n; ++i) { dsu[i] = i; } for (int i = 0; i < m; ++i) { int u, v, d; cin >> u >> v >> d; if (d == 2) { unite(u, v); } else { graph[find(u)].insert(find(v)); } } for (int iter = 0; iter < n + 1; ++iter) { for (int i = 1; i <= n; ++i) { if (vis[find(i)] != vis_cnt) { findCycles(find(i), 0); } } vis_cnt++; } memset(dp, -1, sizeof(dp)); sort(west.begin(), west.end(), greater<pair<int,int>>()); for (auto x : west) { int res = dfs(find(pos[x])); cout << res << "\n"; ++vis_cnt; } }
#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...