# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
877086 | 2023-11-22T20:33:51 Z | MilosMilutinovic | 장난감 기차 (IOI17_train) | C++14 | 157 ms | 1876 KB |
#include "train.h" #include <bits/stdc++.h> using namespace std; vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) { int n = (int) a.size(); int m = (int) u.size(); vector<vector<int>> g(n); vector<vector<int>> t(n); for (int i = 0; i < m; i++) { g[u[i]].push_back(v[i]); t[v[i]].push_back(u[i]); } vector<bool> rem(n); auto CalcA = [&](vector<int> f) { vector<int> que = f; vector<int> deg(n); for (int i = 0; i < n; i++) { if (rem[i]) { continue; } if (a[i] == 0) { deg[i] = (int) g[i].size(); } else { deg[i] = 1; } } for (int x : que) { deg[x] = 0; } for (int b = 0; b < (int) que.size(); b++) { int x = que[b]; for (int y : t[x]) { if (deg[y] <= 0) { continue; } deg[y] -= 1; if (deg[y] == 0) { que.push_back(y); } } } return que; }; auto CalcB = [&](vector<int> f) { vector<int> que = f; vector<int> deg(n); for (int i = 0; i < n; i++) { if (rem[i]) { continue; } if (a[i] == 0) { deg[i] = 1; } else { deg[i] = (int) g[i].size(); } } for (int x : que) { deg[x] = 0; } for (int b = 0; b < (int) que.size(); b++) { int x = que[b]; for (int y : t[x]) { if (deg[y] <= 0) { continue; } deg[y] -= 1; if (deg[y] == 0) { que.push_back(y); } } } return que; }; vector<int> ans(n); while (true) { vector<int> c; for (int i = 0; i < n; i++) { if (r[i] == 1 && !rem[i]) { c.push_back(i); } } vector<int> v = CalcA(c); int cnt = 0; for (int i = 0; i < n; i++) { if (!rem[i]) { cnt += 1; } } if (v.size() == cnt) { for (int x : v) { ans[x] = 1; } break; } vector<bool> in(n); for (int x : v) { in[x] = true; } vector<int> vec; for (int i = 0; i < n; i++) { if (!rem[i] && !in[i]) { vec.push_back(i); } } vector<int> bad = CalcB(vec); for (int x : bad) { rem[x] = true; } } return ans; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 1112 KB | Output is correct |
2 | Correct | 4 ms | 1116 KB | Output is correct |
3 | Correct | 4 ms | 1116 KB | Output is correct |
4 | Correct | 4 ms | 1372 KB | Output is correct |
5 | Correct | 4 ms | 1116 KB | Output is correct |
6 | Correct | 4 ms | 1116 KB | Output is correct |
7 | Correct | 3 ms | 1368 KB | Output is correct |
8 | Correct | 6 ms | 1208 KB | Output is correct |
9 | Correct | 4 ms | 1112 KB | Output is correct |
10 | Correct | 3 ms | 1316 KB | Output is correct |
11 | Correct | 3 ms | 1112 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 0 ms | 600 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 440 KB | Output is correct |
7 | Correct | 0 ms | 344 KB | Output is correct |
8 | Incorrect | 0 ms | 348 KB | 3rd lines differ - on the 2nd token, expected: '0', found: '1' |
9 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 63 ms | 1668 KB | Output is correct |
2 | Correct | 117 ms | 1616 KB | Output is correct |
3 | Correct | 157 ms | 1580 KB | Output is correct |
4 | Correct | 6 ms | 1372 KB | Output is correct |
5 | Incorrect | 6 ms | 1628 KB | 3rd lines differ - on the 11th token, expected: '0', found: '1' |
6 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 1372 KB | Output is correct |
2 | Correct | 6 ms | 1624 KB | Output is correct |
3 | Correct | 6 ms | 1624 KB | Output is correct |
4 | Correct | 6 ms | 1652 KB | Output is correct |
5 | Correct | 7 ms | 1624 KB | Output is correct |
6 | Correct | 6 ms | 1628 KB | Output is correct |
7 | Correct | 6 ms | 1724 KB | Output is correct |
8 | Correct | 5 ms | 1624 KB | Output is correct |
9 | Correct | 5 ms | 1628 KB | Output is correct |
10 | Correct | 6 ms | 1600 KB | Output is correct |
11 | Correct | 6 ms | 1604 KB | Output is correct |
12 | Correct | 6 ms | 1628 KB | Output is correct |
13 | Correct | 6 ms | 1876 KB | Output is correct |
14 | Correct | 6 ms | 1628 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 1372 KB | Output is correct |
2 | Correct | 6 ms | 1640 KB | Output is correct |
3 | Correct | 6 ms | 1700 KB | Output is correct |
4 | Correct | 5 ms | 1628 KB | Output is correct |
5 | Correct | 1 ms | 348 KB | Output is correct |
6 | Correct | 3 ms | 1116 KB | Output is correct |
7 | Correct | 4 ms | 1116 KB | Output is correct |
8 | Correct | 4 ms | 1216 KB | Output is correct |
9 | Correct | 4 ms | 1116 KB | Output is correct |
10 | Correct | 1 ms | 604 KB | Output is correct |
11 | Correct | 3 ms | 1116 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 1112 KB | Output is correct |
2 | Correct | 4 ms | 1116 KB | Output is correct |
3 | Correct | 4 ms | 1116 KB | Output is correct |
4 | Correct | 4 ms | 1372 KB | Output is correct |
5 | Correct | 4 ms | 1116 KB | Output is correct |
6 | Correct | 4 ms | 1116 KB | Output is correct |
7 | Correct | 3 ms | 1368 KB | Output is correct |
8 | Correct | 6 ms | 1208 KB | Output is correct |
9 | Correct | 4 ms | 1112 KB | Output is correct |
10 | Correct | 3 ms | 1316 KB | Output is correct |
11 | Correct | 3 ms | 1112 KB | Output is correct |
12 | Correct | 0 ms | 344 KB | Output is correct |
13 | Correct | 0 ms | 600 KB | Output is correct |
14 | Correct | 0 ms | 348 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Correct | 0 ms | 348 KB | Output is correct |
17 | Correct | 0 ms | 440 KB | Output is correct |
18 | Correct | 0 ms | 344 KB | Output is correct |
19 | Incorrect | 0 ms | 348 KB | 3rd lines differ - on the 2nd token, expected: '0', found: '1' |
20 | Halted | 0 ms | 0 KB | - |