Submission #970434

#	Time	Username	Problem	Language	Result	Execution time	Memory
970434		Itamar	Toy Train (IOI17_train)	C++14	100 / 100	1703 ms	1628 KiB

train

#include "train.h"
#include <vector>
using namespace std;
#define ll long long
#define vi vector<int>
#define pi pair<int,int>
#include <algorithm>
#define x first
#define y second
#define vll vector<ll>
#define pll pair<ll,ll>
#define vb vector<bool>
int n, m;
const int siz = 5e3 + 1;
vi fr[siz];
vi invf[siz];
#include <queue>
int a[siz];
int deg[siz];
void func(vi& bad) {
	vector<bool> vis(n);
	queue<int> q;
	for (int i = 0; i < n; i++)if (bad[i])q.push(i);
	for (int i = 0; i < n; i++)deg[i] = fr[i].size();
	while (!q.empty()) {
		int i = q.front();
		q.pop();
		if (vis[i])continue;
		vis[i] = 1;
		bad[i] = 1;
		for (int f : invf[i]) {
			if (vis[f])continue;
			deg[f]--;
			if (a[f] == 1) {
				if (deg[f] == fr[f].size() - 1)q.push(f);
			}
			else {
				if (deg[f] == 0)q.push(f);
			}
		}
	}
}

vi who_wins(vi A, vi R, vi U, vi V) {
	n = R.size(), m = U.size();
	for (int i = 0; i < n; i++)a[i] = A[i];
	for (int i = 0; i < m; i++) {
		fr[U[i]].push_back(V[i]);
		invf[V[i]].push_back(U[i]);
	}
	vi bad(n,1);
	for (int it = 0; it <= n; it++) {
		vi badt(n);
		for (int i = 0; i < n; i++) {
			//if (bad[i]) {
			if (A[i]) {
				bool g = 0;
				for (int j : fr[i])if (bad[j])g = 1;
				if (g == 0)badt[i] = 0;
				else badt[i] = 1;
			}
			else {
				for (int j : fr[i]) {
					if (bad[j] == 0) {
						badt[i] = 0;
						break;
					}
					if (j == fr[i].back())badt[i] = 1;
				}
			}
			//}
		}
		bad = badt;

		vi badtt = R; for (int i = 0; i < n; i++)if (bad[i] == 0)badtt[i] = 0;
		func(badtt);
		for (int i = 0; i < n; i++)if (badtt[i] == 0)bad[i] = 0;
	}
	return bad;
}

Compilation message (stderr)

train.cpp: In function 'void func(std::vector<int>&)':
train.cpp:35:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     if (deg[f] == fr[f].size() - 1)q.push(f);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~

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