Submission #1243129

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243129		Tob	Toy Train (IOI17_train)	C++20	100 / 100	492 ms	1324 KiB

train

#include <bits/stdc++.h>

#include "train.h"

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int N = 5007;

int n, m;
int a[N], r[N], rdeg[N];
vector <int> adj[N];

vector <int> f(int o, vector <int> v) {
	queue <int> q;
	vector <int> deg(n, 0);
	for (int i = 0; i < n; i++) if (v[i]) q.push(i);
	while (!q.empty()) {
		int x = q.front(); q.pop();
		for (int y : adj[x]) if (!v[y]) {
			deg[y]++;
			if (a[y] == o) v[y] = 1, q.push(y);
			else if (deg[y] == rdeg[y]) v[y] = 1, q.push(y);
		}
	}
	return v;
}

vector <int> who_wins(vector <int> aa, vector <int> rr, vector <int> u, vector <int> v) {
	n = aa.size(), m = u.size();
	for (int i = 0; i < n; i++) a[i] = aa[i], r[i] = rr[i];
	for (int i = 0; i < m; i++) adj[v[i]].pb(u[i]), rdeg[u[i]]++;
	vector <int> d(n, 1);
	while (1) {
		vector <int> u(n, 1), c(n, 0);
		for (int i = 0; i < n; i++) if (d[i] && r[i]) c[i] = 1;
		c = f(1, c);
		int ok = 1;
		for (int i = 0; i < n; i++) {
			if (d[i] && c[i]) u[i] = 0;
			if (d[i] && !c[i]) ok = 0;
		}
		if (ok) break;
		u = f(0, u);
		for (int i = 0; i < n; i++) if (d[i] && u[i]) d[i] = 0;
	}
	return d;
}

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