# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1045561 | pcc | Toy Train (IOI17_train) | C++17 | 536 ms | 4440 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "train.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn = 5050;
vector<int> charge;
int N,M;
queue<int> q;
int owner[mxn];
bitset<mxn> reach[mxn],dist;
vector<int> paths[mxn];
void BFS(int s = -1){
if(s != -1){
dist.reset();
q.push(s);
}
while(!q.empty()){
auto now = q.front();
q.pop();
for(auto nxt:paths[now]){
if(!dist[nxt]){
dist[nxt] = 1;
q.push(nxt);
}
}
}
return;
}
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
N = a.size();
assert(r.size() == a.size());
for(int i = 0;i<N;i++){
owner[i] = a[i];
if(r[i])charge.push_back(i);
}
for(int i = 0;i<u.size();i++){
int aa = u[i],bb = v[i];
paths[aa].push_back(bb);
}
for(int i = 0;i<N;i++){
BFS(i);
reach[i] = dist;
}
vector<int> ans(N);
for(int i = 0;i<N;i++){
for(auto &j:charge){
if(reach[i][j]&&reach[j][j])ans[i] = 1;
}
}
return ans;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |