Submission #1246137

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246137		Quentolosse	Toy Train (IOI17_train)	C++20	0 / 100	68 ms	1288 KiB

train

#include "train.h"

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

std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
	int n = a.size();
	int m = u.size();

	int k = 0;
	for (auto &&i : r)
	{
		k += i;
	}

	vector<int> nb_sortantes(n, 0);
	for (auto &&i : u)
	{
		nb_sortantes[i]++;
	}
	
	vector<vector<int>> graphe_inv(n);
	for (int i = 0; i < m; i++)
	{
		graphe_inv[v[i]].push_back(u[i]);
	}
	
	vector<int> avant(n, true);
	
	for (int _ = 0; _ < k+42; _++)
	{
		vector<int> actuels(n, 0);
		vector<int> pile;
		vector<int> s;
		s = nb_sortantes;

		for (int i = 0; i < n; i++)
		{
			if (r[i] && avant[i]) {
				pile.push_back(i);
			}
		}
		
		while(!pile.empty()) {
			int c = pile.back();
			pile.pop_back();

			if (actuels[c] == 1) continue;

			if (actuels[c] == 0 && r[c]) {
				actuels[c] = -1;
			}
			else {
				if (r[c]) continue;
				actuels[c] = true;
			}

			for (auto &&i : graphe_inv[c])
			{
				if (actuels[i] == 1) continue;
				if (a[i]) pile.push_back(i);
				else if (--s[i] == 0) pile.push_back(i);
			}
		}

		for (auto &&i : actuels)
		{
			if (i == -1) i = 0;
		}
		

		avant = actuels;
	}
	
	return avant;

}

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