Submission #1246079

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246079		raphaelp	Toy Train (IOI17_train)	C++20	100 / 100	227 ms	1552 KiB

train

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

vector<int> who_wins(vector<int> Own, vector<int> Charge, vector<int> U, vector<int> V) {
	int N = Own.size();
	vector<vector<int>> AR(N), AR2(N);
	int M = U.size();
	for (int i=0; i<M; i++)
	{
		AR[U[i]].push_back(V[i]);
		AR2[V[i]].push_back(U[i]);
	}
	vector<int> occ(N);
	while(true)
	{
		vector<int> left(N);
		occ.assign(N, 0);
		for (int i=0; i<N; i++)left[i]=AR[i].size();
		queue<int> Q;
		for (int i=0; i<N; i++)
		{
			if (Charge[i]==0)continue;
			Q.push(i);
			occ[i]=1;
		}		
		while(!Q.empty())
		{
			int x = Q.front();
			Q.pop();
			for (int i=0; i<AR2[x].size(); i++)
			{
				if (occ[AR2[x][i]])continue;
				left[AR2[x][i]]--;
				if (Own[AR2[x][i]]==1 || left[AR2[x][i]]==0)
				{
					occ[AR2[x][i]]=1;
					Q.push(AR2[x][i]);
				}
			}
		}
		int rem=0;
		for (int i=0; i<N; i++)
		{
			if (Charge[i]==0)continue;
			int cnt=0;
			for (int j=0; j<AR[i].size(); j++)
				cnt+=occ[AR[i][j]];
			if (cnt==0 || (cnt<AR[i].size() && Own[i]==0)){
				rem=1;
				Charge[i]=0;
			}
		}
		if (rem==0)break;
	}
	return occ;
}

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