# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
783530 | 2023-07-15T03:04:48 Z | vjudge1 | Toy Train (IOI17_train) | C++17 | 7 ms | 4076 KB |
#include "train.h" #include<bits/stdc++.h> using namespace std; vector<int> adj[50100], adj2[50100]; int lowl[50100], id[50100], onstk[50100], cnt, sz[50100], ok[50100], charged[50100], vis[50100]; stack<int> stk; void tarjan(int n) { if(id[n]) return; lowl[n] = id[n] = ++cnt; onstk[n] = 1; stk.push(n); for(auto i: adj[n]) { tarjan(i); if(onstk[i]) { lowl[n] = min(lowl[i], lowl[n]); } } sz[lowl[n]]++; if(lowl[n] == id[n]) { while(stk.top()!=n) { onstk[stk.top()]=0; stk.pop(); } onstk[n] = 0; stk.pop(); } } vector<int> order; void dfs(int n) { if(vis[n]) return; vis[n] = 1; for(auto i: adj2[n]) dfs(i); order.push_back(n); } std::vector<int> who_wins(std::vector<int> A, std::vector<int> R, std::vector<int> u, std::vector<int> v) { for(int i = 0; i < u.size(); i++) { adj[u[i]].push_back(v[i]); if(u[i]==v[i]) ok[u[i]] = 1; } for(int i = 0; i < A.size(); i++) { tarjan(i); } for(int i = 0; i < cnt; i++) { if(R[i]&&(sz[lowl[i]]!=1||ok[i])) { charged[lowl[i]]++; } } for(int i = 0; i < u.size(); i++) adj2[lowl[u[i]]].push_back(lowl[v[i]]); for(int i = 1; i <= cnt; i++) { dfs(lowl[i]); } for(auto i: order) { for(auto j: adj2[i]) if(charged[j]) charged[i] = 1; } vector<int> res; for(int i = 0; i < cnt; i++) { res.push_back(charged[lowl[i]]); } return res; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 5 ms | 3848 KB | 3rd lines differ - on the 2nd token, expected: '0', found: '1' |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 2664 KB | 3rd lines differ - on the 8th token, expected: '0', found: '1' |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 4076 KB | Output is correct |
2 | Correct | 6 ms | 4052 KB | Output is correct |
3 | Correct | 6 ms | 3924 KB | Output is correct |
4 | Correct | 7 ms | 3924 KB | Output is correct |
5 | Correct | 7 ms | 3824 KB | Output is correct |
6 | Incorrect | 7 ms | 3796 KB | 3rd lines differ - on the 200th token, expected: '1', found: '0' |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 3668 KB | 3rd lines differ - on the 696th token, expected: '0', found: '1' |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 3956 KB | 3rd lines differ - on the 2nd token, expected: '0', found: '1' |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 5 ms | 3848 KB | 3rd lines differ - on the 2nd token, expected: '0', found: '1' |
2 | Halted | 0 ms | 0 KB | - |