# IOI 2017 – Toy Train Problem and Solution The 29th International Olympiad in Informatics was held in Tehran, Iran in 2017. There were two competition days, with 3 problems given to the competitors on each day. You can see the Toy Train problem and solutions below.

ioi2017problem3

### SOLUTION – TOY TRAIN :

``````#include "train.h"
#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<int> gph;
vector<int> proc;

vector<int> always(vector<int> &a, vector<int> &v, int winner){
vector<int> deg(n);
queue<int> que;
for(int i=0; i<n; i++){
if(proc[i]) continue;
for(auto &j : gph[i]){
if(!proc[j]) deg[j]++;
}
}
for(auto &i : v){
if(deg[i] > 0){
deg[i] = 0;
}
que.push(i);
}
vector<int> ret;
while(!que.empty()){
int x = que.front(); que.pop();
ret.push_back(x);
for(auto &i : gph[x]){
if(proc[i]) continue;
if(a[i] == winner && deg[i] > 0){
deg[i] = 0;
que.push(i);
}
else if(a[i] != winner){
deg[i]--;
if(deg[i] == 0) que.push(i);
}
}
}
return ret;
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v){
n = a.size();
m = u.size();
vector<int> ret(n);
proc.resize(n);
for(int i=0; i<m; i++){
gph[v[i]].push_back(u[i]);
}
while(true){
int unproc = count(proc.begin(), proc.end(), 0);
if(unproc == 0) break;
vector<int> R;
for(int i=0; i<n; i++) if(!proc[i] && r[i]) R.push_back(i);
R = always(a, R, 1);
if(R.size() == unproc){
for(auto &i : R) proc[i] = 1, ret[i] = 1;
}
else{
vector<int> rem(n);
for(auto &i : R) rem[i] = 1;
R.clear();
for(int i=0; i<n; i++){
if(!proc[i] && !rem[i]) R.push_back(i);
}
R = always(a, R, 0);
for(auto &i : R) proc[i] = 1, ret[i] = 0;
}
}
return ret;
}``````

### EXPLANATION :

train

40 total views,  1 views today

#### Post Disclaimer

The hole problem statement are given by ioinformatics.org but the solution are generated by the sltechacademy authority if any of the query regarding this post or website fill the following contact form thank you.