Submission #440575

#	Time	Username	Problem	Language	Result	Execution time	Memory
440575		prvocislo	Toy Train (IOI17_train)	C++17	100 / 100	656 ms	1732 KiB

train

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

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
	int n = a.size(), m = u.size();
	vector<int> res(n);
	bool change = true;
	vector<vector<int> > g(n), gt(n);
	for (int i = 0; i < m; i++) g[u[i]].push_back(v[i]), gt[v[i]].push_back(u[i]);
	while (change)
	{
		res.assign(n, false);
		vector<int> mn, deg(n, 0); // mnozina ktora caka na spracovanie
		for (int i = 0; i < m; i++) deg[u[i]]++;
		for (int i = 0; i < n; i++) 
		{
			if (r[i]) mn.push_back(i), res[i] = true;
			if (a[i]) deg[i] = 1;
		}
		while (!mn.empty())
		{
			int vr = mn.back(); mn.pop_back();
			for (int to : gt[vr])
			{
				deg[to]--;
				if (deg[to] == 0 && !res[to]) mn.push_back(to), res[to] = true;
			}
		}
		change = false;
		for (int i = 0; i < n; i++)
		{
			if (!r[i]) continue;
			int cnt = 0;
			for (int to : g[i])
				if (res[to]) cnt++;
			if ((a[i] && !cnt) || (!a[i] && cnt < g[i].size()))
			{
				change = true;
				r[i] = false;
			}
		}
	}
	return res;
}

Compilation message (stderr)

train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:37:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |    if ((a[i] && !cnt) || (!a[i] && cnt < g[i].size()))
      |                                    ~~~~^~~~~~~~~~~~~

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