Submission #74375

#	Time	Username	Problem	Language	Result	Execution time	Memory
74375		Diuven	Toy Train (IOI17_train)	C++14	100 / 100	856 ms	9548 KiB

train

#include "train.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
const int MX=5010;

vector<int> G[MX], H[MX];
int n;
bool tmp[MX];
vi win, A, R;

const vi& find(const vi &S, bool c){
	static bool in[MX]={}; int deg[MX]={};
	static vi T; static queue<int> Q;

	for(int i=0; i<n; i++) in[i]=false, deg[i]=0;
	T.clear();
	for(int i=0; i<n; i++) if(win[i]<0)
		for(int x:G[i]) deg[i]+=win[x]<0;

	for(int x:S) in[x]=true, Q.push(x);

	while(!Q.empty()){
		int v=Q.front(); Q.pop();
		for(int x:H[v]){
			if(in[x] || win[x]>=0) continue;
			if(A[x]==c) in[x]=true, Q.push(x);
			else{
				deg[x]--;
				if(deg[x]==0) in[x]=true, Q.push(x);
			}
		}
	}

	for(int i=0; i<n; i++) if(in[i]) T.push_back(i);

	return T;
}

vi who_wins(vi _A, vi _R, vi U, vi V) {
	n=_A.size(); win.resize(n, -1);
	A=_A, R=_R;

	for(int i=0; i<(int)U.size(); i++){
		G[U[i]].push_back(V[i]);
		H[V[i]].push_back(U[i]);
	}

	vi S, T, X, Y;
	while(true){
		S.clear(), X.clear();
		for(int i=0; i<n; i++) if(R[i] && win[i]<0) S.push_back(i);
		T=find(S, 1);

		for(int i=0; i<n; i++) tmp[i]=win[i]>=0;
		for(int x:T) tmp[x]=true;
		for(int i=0; i<n; i++) if(!tmp[i]) X.push_back(i);

		if(X.empty()){
			for(int x:T) win[x]=1;
			break;
		}
		else{
			Y=find(X, 0);
			for(int x:Y) win[x]=0;
		}
	}

	return win;
}

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