oj.uz

Submission #430553

# Submission time Handle Problem Language Result Execution time Memory
430553 2021-06-16T15:48:45 Z rainboy Toy Train (IOI17_train) C++
0 / 100
 1397 ms 98872 KB 
#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_ + 1] == 0)
						qu[cnt++] = j * (n + 1) + t_;
		}
	}
	for (i = 0; i < n; i++)
		ans[i] = dd[i][n] >= 0;
	return ans;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 212 ms 98628 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 1 ms 332 KB 3rd lines differ - on the 8th token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 820 ms 98844 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 84 ms 98680 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 Correct 1397 ms 98844 KB Output is correct
2 Correct 111 ms 98740 KB Output is correct
3 Correct 569 ms 98872 KB Output is correct
4 Correct 108 ms 98736 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 1367 ms 98616 KB Output is correct
7 Correct 25 ms 3660 KB Output is correct
8 Incorrect 37 ms 3748 KB 3rd lines differ - on the 5th token, expected: '0', found: '1'
9 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

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