제출 #672697

#제출 시각아이디문제언어결과실행 시간메모리
672697haxormanTraffic (CEOI11_tra)C++14
8 / 100
5023 ms59900 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]; 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]) { unite(u, prev); return; } st[u] = true; 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 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 p : west) { int res = dfs(find(pos[p])); 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...