Submission #430568

#	Time	Username	Problem	Language	Result	Execution time	Memory
430568		rainboy	Toy Train (IOI17_train)	C++98	100 / 100	1982 ms	117996 KiB

train

#include "train.h"
#include <stdlib.h>

using namespace std;

const int N = 5000;

typedef vector<int> vi;

int *ej[N], eo[N], dd[N][N + 1], out[N], qu[N * (N + 1)], n; char rr[N];

vi who_wins(vi aa, vi rr_, vi uu, vi vv) {
	int m = uu.size(), h, i, j, t, t_, cnt;
	vi ans(n = aa.size());

	for (i = 0; i < n; i++)
		rr[i] = rr_[i];
	for (h = 0; h < m; h++)
		out[uu[h]]++, eo[vv[h]]++;
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(eo[i] * sizeof *ej[i]), eo[i] = 0;
	for (h = 0; h < m; h++)
		ej[vv[h]][eo[vv[h]]++] = uu[h];
	for (i = 0; i < n; i++) {
		dd[i][0] = !rr[i] ? 1 : 0;
		for (t = 1; t <= n; t++)
			dd[i][t] = t == n || !rr[i] ? (aa[i] ? out[i] : 1) : 0;
	}
	cnt = 0;
	for (i = 0; i < n; i++)
		if (--dd[i][0] == 0)
			qu[cnt++] = i * (n + 1) + 0;
	while (cnt) {
		int it = qu[--cnt], o;

		i = it / (n + 1), t = it % (n + 1);
		dd[i][t] = -1;
		for (o = eo[i]; o--; ) {
			j = ej[i][o];
			if (t != n) {
				if (--dd[j][t + 1] == 0)
					qu[cnt++] = j * (n + 1) + t + 1;
			} else if (rr[i])
				for (t_ = 1; t_ <= n; t_++)
					if (--dd[j][t_] == 0)
						qu[cnt++] = j * (n + 1) + t_;
		}
	}
	for (i = 0; i < n; i++)
		ans[i] = dd[i][n] >= 0;
	return ans;
}

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