Submission #646259

#	Time	Username	Problem	Language	Result	Execution time	Memory
646259		jamezzz	Toy Train (IOI17_train)	C++17	11 / 100	566 ms	1272 KiB

train

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

#define maxn 5005

typedef vector<int> vi;
bool vis[maxn],good[maxn];
vi AL[maxn];

vi who_wins(vi a,vi r,vi u,vi v){
	int n=a.size(),m=u.size();
	vi ans(n,0);
	for(int i=0;i<m;++i){
		AL[u[i]].push_back(v[i]);
	}
	for(int i=0;i<n;++i){
		if(r[i]==1)continue;
		for(int j=0;j<n;++j)vis[j]=false;
		queue<int> q;
		q.push(i);
		while(!q.empty()){
			int u=q.front();
			q.pop();
			if(good[i])continue;
			for(int v:AL[u]){
				if(r[v]==1)continue;
				if(v==i)good[i]=true;
				if(vis[v])continue;
				vis[v]=true;
				q.push(v);
			}
		}
	}
	for(int i=0;i<n;++i){
		bool take=false;
		for(int j=0;j<n;++j){
			for(int k:AL[j]){
				if(good[k]){
					good[j]=true;
					take=true;
					break;
				}
			}
		}
		if(!take)break;
	}
	for(int i=0;i<n;++i)ans[i]=!good[i];
	return ans;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 11
• Subtask 4: 11 / 11
• Subtask 5: 0 / 12
• Subtask 6: 0 / 51