# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
289025 | 2020-09-02T09:39:11 Z | AlexLuchianov | Toy Train (IOI17_train) | C++14 | 11 ms | 1668 KB |
#include "train.h" #include <queue> #include <iostream> std::vector<std::vector<int>> g, depend; int refresh(int node, std::vector<int> &own, std::vector<int> &state) { if(own[node] == 1) { for(int h = 0; h < g[node].size();h ++) { int to = g[node][h]; if(state[to] == 1) return 1; } return 0; } else { for(int h = 0; h < g[node].size(); h++) { int to = g[node][h]; if(state[to] == 0) return 0; } return 1; } } std::vector<int> first_phase(std::vector<int> own, std::vector<int> r) { int n = own.size(); std::vector<int> state(n); std::queue<int> q; for(int i = 0; i < n; i++) if(r[i] == 1) { state[i] = 1; q.push(i); } while(0 < q.size()) { int node = q.front(); q.pop(); for(int h = 0; h < depend[node].size(); h++) { int to = depend[node][h]; if(state[to] == 0) { state[to] = refresh(to, own, state); if(state[to] == 1) q.push(to); } } } return state; } int refresh2(int node, std::vector<int> &own, std::vector<int> &state) { if(own[node] == 1) { for(int h = 0; h < g[node].size(); h++) { int to = g[node][h]; if(state[to] == 0) return 0; } return 1; } else { for(int h = 0; h < g[node].size(); h++) { int to = g[node][h]; if(state[to] == 1) return 1; } return 0; } } std::vector<int> second_phase(std::vector<int> &own, std::vector<int> &init) { int n = own.size(); std::vector<int> state(own.size()); std::queue<int> q; for(int i = 0; i < n; i++) if(init[i] == 0) { state[i] = 1; q.push(i); } while(0 < q.size()) { int node = q.front(); q.pop(); for(int h = 0; h < depend[node].size(); h++) { int to = depend[node][h]; if(state[to] == 0) { state[to] = refresh2(to, own, state); if(state[to] == 1) { q.push(to); } } } } return state; } std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) { std::vector<int> res(a.size()); int n = a.size(); g.clear(); depend.clear(); g.resize(n); depend.resize(n); for(int i = 0; i < u.size(); i++) { g[u[i]].push_back(v[i]); depend[v[i]].push_back(u[i]); } std::vector<int> state = first_phase(a, r); std::vector<int> state2 = second_phase(a, state); for(int i = 0; i < n; i++) res[i] = !state2[i]; return res; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 1152 KB | 3rd lines differ - on the 1st token, expected: '0', found: '1' |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 256 KB | Output is correct |
2 | Correct | 1 ms | 256 KB | Output is correct |
3 | Correct | 0 ms | 256 KB | Output is correct |
4 | Incorrect | 1 ms | 384 KB | 3rd lines differ - on the 4th token, expected: '0', found: '1' |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 8 ms | 1536 KB | 3rd lines differ - on the 1st token, expected: '0', found: '1' |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 1280 KB | Output is correct |
2 | Correct | 9 ms | 1536 KB | Output is correct |
3 | Correct | 10 ms | 1664 KB | Output is correct |
4 | Correct | 10 ms | 1664 KB | Output is correct |
5 | Correct | 10 ms | 1668 KB | Output is correct |
6 | Correct | 10 ms | 1664 KB | Output is correct |
7 | Correct | 10 ms | 1664 KB | Output is correct |
8 | Correct | 9 ms | 1664 KB | Output is correct |
9 | Correct | 9 ms | 1536 KB | Output is correct |
10 | Correct | 10 ms | 1664 KB | Output is correct |
11 | Correct | 10 ms | 1664 KB | Output is correct |
12 | Correct | 10 ms | 1664 KB | Output is correct |
13 | Correct | 10 ms | 1664 KB | Output is correct |
14 | Correct | 9 ms | 1536 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 1408 KB | Output is correct |
2 | Correct | 10 ms | 1664 KB | Output is correct |
3 | Correct | 11 ms | 1664 KB | Output is correct |
4 | Correct | 10 ms | 1536 KB | Output is correct |
5 | Correct | 2 ms | 384 KB | Output is correct |
6 | Correct | 5 ms | 1152 KB | Output is correct |
7 | Correct | 7 ms | 1024 KB | Output is correct |
8 | Incorrect | 7 ms | 1024 KB | 3rd lines differ - on the 5th token, expected: '0', found: '1' |
9 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 1152 KB | 3rd lines differ - on the 1st token, expected: '0', found: '1' |
2 | Halted | 0 ms | 0 KB | - |