oj.uz

Submission #430502

# Submission time Handle Problem Language Result Execution time Memory
430502 2021-06-16T14:55:44 Z rainboy Toy Train (IOI17_train) C++
0 / 100
 1749 ms 262148 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;

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
			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());

	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:39:27: warning: unused variable 'j' [-Wunused-variable]
   39 |  int m = uu.size(), h, i, j, t;
      |                           ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 232 ms 98948 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 105 ms 98780 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 Correct 83 ms 99084 KB Output is correct
2 Correct 506 ms 99376 KB Output is correct
3 Correct 1749 ms 99488 KB Output is correct
4 Correct 1218 ms 108064 KB Output is correct
5 Correct 847 ms 124936 KB Output is correct
6 Correct 626 ms 105712 KB Output is correct
7 Correct 582 ms 123024 KB Output is correct
8 Correct 1578 ms 102232 KB Output is correct
9 Correct 272 ms 100096 KB Output is correct
10 Correct 90 ms 99104 KB Output is correct
11 Correct 92 ms 99000 KB Output is correct
12 Correct 102 ms 98972 KB Output is correct
13 Runtime error 249 ms 262148 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 303 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

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