Submission #431248

#	Time	Username	Problem	Language	Result	Execution time	Memory
431248		rainboy	Toy Train (IOI17_train)	C++98	100 / 100	416 ms	1328 KiB

train

/* https://codeforces.com/blog/entry/53550?#comment-375660 (Swistakk) */
#include "train.h"
#include <stdlib.h>

using namespace std;

const int N = 5000;

typedef vector<int> vi;

int *ej[N], eo[N], dd_[N], dd[N], qu[N]; char rr[N];

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

	for (i = 0; i < n; i++)
		rr[i] = rr_[i];
	for (h = 0; h < m; h++)
		dd_[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];
again:
	cnt = 0;
	for (i = 0; i < n; i++) {
		dd[i] = aa[i] == 1 ? 1 : dd_[i], ans[i] = 0;
		if (rr[i])
			dd[i] = 0, ans[i] = 1, qu[cnt++] = i;
	}
	while (cnt) {
		i = qu[--cnt];
		for (o = eo[i]; o--; ) {
			j = ej[i][o];
			if (--dd[j] == 0)
				ans[j] = 1, qu[cnt++] = j;
		}
	}
	cnt = 0;
	for (i = 0; i < n; i++) {
		dd[i] = aa[i] == 0 ? 1 : dd_[i];
		if (!ans[i])
			dd[i] = 0, qu[cnt++] = i;
	}
	while (cnt) {
		i = qu[--cnt];
		for (o = eo[i]; o--; ) {
			j = ej[i][o];
			if (--dd[j] == 0) {
				ans[j] = 0, qu[cnt++] = j;
				if (rr[j]) {
					rr[j] = 0;
					goto again;
				}
			}
		}
	}
	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