oj.uz

Submission #431242

# Submission time Handle Problem Language Result Execution time Memory
431242 2021-06-17T10:29:54 Z rainboy Toy Train (IOI17_train) C++
0 / 100
 19 ms 1200 KB 
/* 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] == 1) {
				ans[j] = 0, qu[cnt++] = j;
				if (rr[j]) {
					rr[j] = 0;
					goto again;
				}
			}
		}
	}
	return ans;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 840 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 1200 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 972 KB 3rd lines differ - on the 696th token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 1072 KB 3rd lines differ - on the 60th token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 840 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -