# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
672697 |
2022-12-17T13:38:05 Z |
haxorman |
Traffic (CEOI11_tra) |
C++14 |
|
5000 ms |
59900 KB |
#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 time |
Memory |
Grader output |
1 |
Correct |
8 ms |
15572 KB |
Output is correct |
2 |
Correct |
8 ms |
15492 KB |
Output is correct |
3 |
Correct |
9 ms |
15572 KB |
Output is correct |
4 |
Correct |
9 ms |
15568 KB |
Output is correct |
5 |
Correct |
8 ms |
15572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
15572 KB |
Output is correct |
2 |
Incorrect |
10 ms |
15572 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
8 ms |
15572 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
11 ms |
15944 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5023 ms |
18372 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
184 ms |
22656 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1772 ms |
29340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
947 ms |
31768 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
983 ms |
43808 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1152 ms |
59744 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
602 ms |
59900 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
524 ms |
50160 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |