# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
789651 | esomer | Toy Train (IOI17_train) | C++17 | 7 ms | 1296 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<bits/stdc++.h>
#include "train.h"
using namespace std;
typedef long long ll;
void process(vector<int>& A, vector<int>& R, vector<int>& U, vector<int>& V, vector<bool>& forced, vector<int>& out, vector<vector<int>>& radj){
int n = (int)A.size();
int m = (int)U.size();
queue<int> q;
for(int i = 0; i < n; i++){
if(out[i] == 0){
forced[i] = 0;
q.push(i);
}
}
vector<int> org = out;
while(!q.empty()){
int x = q.front(); q.pop();
for(int node : radj[x]){
out[node]--;
if(forced[node] == 0) continue;
if(out[node] == 0) {q.push(node); forced[node] = 0;}
if(A[node] == 1){
forced[node] = 0;
q.push(node);
}
}
}
out = org;
for(int i = 0; i < n; i++){
if(out[i] == 0){
q.push(i);
}
}
while(!q.empty()){
int x = q.front(); q.pop();
for(int node : radj[x]){
out[node]--;
if(forced[node] == 1) continue;
if(out[node] == 0) {q.push(node); forced[node] = 1;}
if(A[node] == 0){
forced[node] = 1;
q.push(node);
}
}
}
out = org;
}
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();
bool stop = 0;
vector<bool> forced; //If 1, then it can be forced by B into a cycle with no R's.
vector<int> out(n);
vector<vector<int>> radj(n);
for(int i = 0; i < m; i++){
out[U[i]]++;
radj[V[i]].push_back(U[i]);
}
while(!stop){
stop = 1;
forced.assign(n, 1);
process(A, R, U, V, forced, out, radj);
for(int i = 0; i < n; i++){
if(forced[i] == 1 && R[i] == 1) {R[i] = 0; stop = 0;}
}
}
vector<int> ans(n);
for(int i = 0; i < n; i++){
if(forced[i] == 1) ans[i] = 0;
else 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... |