# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
132632 | rondojim | Toy Train (IOI17_train) | C++17 | 361 ms | 3072 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<vector>
#include<iostream>
#include<queue>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
vector<int> nei[10000];
vector<int> inv[10000];
bool active[10000];
int owner[10000];
int charge[10000];
int n;
bool S[10000];
int count[10000];
int reference;
void extend(int node){
if(S[node])return;
S[node]=true;
//cout<<node<<endl;
rep(i,0,inv[node].size()){
int v=inv[node][i];
if(active[v]){
count[v]++;
if(!S[v]){
if(reference==owner[v]){
//cout<<v<<endl;
extend(v);
}else{
if(count[v]==nei[v].size()){
extend(v);
}
}
}
}
}
}
void solve(){
//rep(i,0,n)cout<<active[i]<<" ";
//cout<<endl;
reference=1;
rep(i,0,n)count[i]=0;
rep(i,0,n){
S[i]=false;
}
rep(i,0,n){
if(charge[i] && active[i])extend(i);
}
int cont=0;
rep(i,0,n){
if(!S[i] && active[i])S[i]=true;
else S[i]=false;
cont+=S[i];
//cout<<S[i]<<endl;
//cout<<S[i]<<" ";
}//cout<<endl;
if(cont==0)return;
reference=0;
rep(i,0,n)count[i]=0;
queue<int> q;
rep(i,0,n){
if(S[i] && active[i]){
q.push(i);
S[i]=false;
}
}
while(!q.empty()){
extend(q.front());
q.pop();
}
rep(i,0,n){
if(active[i] && S[i]){
active[i]=false;
}
}
solve();
}
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
n=a.size();
rep(i,0,n){
owner[i]=a[i];
charge[i]=r[i];
}
rep(i,0,u.size()){
nei[u[i]].push_back(v[i]);inv[v[i]].push_back(u[i]);
}
rep(i,0,n)active[i]=true;
solve();
vector<int> answer;
rep(i,0,n){
answer.push_back(active[i]);
}
return answer;
}
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... |