# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
33543 | 2017-10-29T17:07:00 Z | mohammad_kilani | Toy Train (IOI17_train) | C++14 | 2000 ms | 3120 KB |
#include <bits/stdc++.h> #include "train.h" using namespace std; const int N = 5010; int n ; bitset< N > dp , vis , win ; vector<int> g[N] , a , r; bool solve(int i, int j){ if(r[i]) return 1; if(i == j && !a[i]) return 1; if(vis[i]) return dp[i]; vis[i] = 1; dp[i] = 1; if(!a[i]){ for(int k=0;k<g[i].size();k++){ int node = g[i][k]; if(solve(node,j) == 0) dp[i] = 0; } } else{ bool can = false; for(int k=0;k<g[i].size();k++){ int node = g[i][k]; if(node != j && solve(node,j) == 1) can = true; } dp[i] = can; } return dp[i]; } bool solve2(int i){ if(win[i] == 0) return 0; if(vis[i]) return dp[i]; vis[i] = 1; dp[i] = 1; if(!a[i]){ for(int k=0;k<g[i].size();k++){ int node = g[i][k]; if(solve2(node) == 0) dp[i] = 0; } } else{ bool can = false; for(int k=0;k<g[i].size();k++){ int node = g[i][k]; if(solve2(node) == 1) can = true; } dp[i] = can; } return dp[i]; } std::vector<int> who_wins(std::vector<int> A, std::vector<int> R, std::vector<int> u, std::vector<int> v) { vector<int> ans; a = A; r = R;; n = a.size(); for(int i=0;i<u.size();i++) g[u[i]].push_back(v[i]); for(int i=0;i<n;i++){ for(int j=0;j<n;j++) vis[j] = 0 ; bool can = 1; for(int j=0;j<g[i].size();j++){ if(solve(g[i][j],i) == 0) can = 0; } win[i] = can; } for(int i=0;i<n;i++){ for(int j=0;j<n;j++) vis[j] = 0 ; bool can = 1; if(solve2(i) == 0) can = 0; win[i] = can; ans.push_back(win[i]); } return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 553 ms | 2820 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 | 2140 KB | Output is correct |
2 | Incorrect | 0 ms | 2140 KB | 3rd lines differ - on the 1st token, expected: '0', found: '1' |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 616 ms | 3120 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 | Incorrect | 1609 ms | 2804 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 | Execution timed out | 2000 ms | 2952 KB | Execution timed out |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 553 ms | 2820 KB | 3rd lines differ - on the 1st token, expected: '0', found: '1' |
2 | Halted | 0 ms | 0 KB | - |