oj.uz

Submission #430528

# Submission time Handle Problem Language Result Execution time Memory
430528 2021-06-16T15:24:42 Z rainboy Toy Train (IOI17_train) C++
11 / 100
 1434 ms 105532 KB 
#include "train.h"
#include <stdlib.h>

using namespace std;

const int N = 5000;

typedef vector<int> vi;

int *ej[N], eo[N];

void append(int i, int j) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]); 
	ej[i][o] = j;
}

int dd[N][N + 1], out[N], n;
vi rr;

void dfs(int i, int t) {
	int o;

	if (dd[i][t]-- != 0)
		return;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o], t_;

		if (t != n)
			dfs(j, t + 1);
		else if (rr[i])
			for (t_ = 1; t_ <= n; t_++)
				dfs(j, t_);
	}
}

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

	rr = rr_;
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (h = 0; h < m; h++) {
		append(vv[h], uu[h]);
		out[uu[h]]++;
	}
	for (i = 0; i < n; i++) {
		dd[i][0] = !rr[i] ? 0 : -1;
		for (t = 1; t <= n; t++)
			dd[i][t] = t == n || !rr[i] ? (aa[i] ? out[i] : 0) : -1;
	}
	for (i = 0; i < n; i++)
		dfs(i, 0);
	for (i = 0; i < n; i++)
		ans[i] = dd[i][n] >= 0;
	return ans;
}

Compilation message

train.cpp: In function 'void append(int, int)':
train.cpp:15:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   15 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
train.cpp: In function 'vi who_wins(vi, vi, vi, vi)':
train.cpp:40:27: warning: unused variable 'j' [-Wunused-variable]
   40 |  int m = uu.size(), h, i, j, t;
      |                           ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 165 ms 98980 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 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 110 ms 98772 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 99120 KB Output is correct
2 Correct 447 ms 99192 KB Output is correct
3 Correct 1434 ms 99292 KB Output is correct
4 Correct 977 ms 105532 KB Output is correct
5 Correct 1097 ms 99660 KB Output is correct
6 Correct 564 ms 99592 KB Output is correct
7 Correct 508 ms 100424 KB Output is correct
8 Correct 1330 ms 100012 KB Output is correct
9 Correct 216 ms 99916 KB Output is correct
10 Correct 89 ms 98760 KB Output is correct
11 Correct 86 ms 98892 KB Output is correct
12 Correct 86 ms 98764 KB Output is correct
13 Correct 1383 ms 99472 KB Output is correct
14 Correct 673 ms 99476 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 51.0

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