oj.uz

Submission #430547

# Submission time Handle Problem Language Result Execution time Memory
430547 2021-06-16T15:39:12 Z rainboy Toy Train (IOI17_train) C++
38 / 100
 2000 ms 108196 KB 
#pragma GCC optimize("O3")
#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;
	dd[i][t] = -1;
	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] ? 1 : 0;
		for (t = 1; t <= n; t++)
			dd[i][t] = t == n || !rr[i] ? (aa[i] ? out[i] : 1) : 0;
	}
	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:16:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   16 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
train.cpp: In function 'vi who_wins(vi, vi, vi, vi)':
train.cpp:42:27: warning: unused variable 'j' [-Wunused-variable]
   42 |  int m = uu.size(), h, i, j, t;
      |                           ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 99252 KB Output is correct
2 Correct 243 ms 99140 KB Output is correct
3 Correct 212 ms 99128 KB Output is correct
4 Correct 217 ms 99132 KB Output is correct
5 Correct 212 ms 99140 KB Output is correct
6 Correct 201 ms 99128 KB Output is correct
7 Correct 270 ms 99136 KB Output is correct
8 Correct 115 ms 99132 KB Output is correct
9 Correct 227 ms 99140 KB Output is correct
10 Correct 221 ms 99116 KB Output is correct
11 Correct 224 ms 99012 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1638 ms 99932 KB Output is correct
2 Correct 1095 ms 100036 KB Output is correct
3 Correct 755 ms 99908 KB Output is correct
4 Correct 247 ms 99448 KB Output is correct
5 Correct 724 ms 99424 KB Output is correct
6 Execution timed out 2001 ms 99396 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 99200 KB Output is correct
2 Correct 367 ms 99272 KB Output is correct
3 Correct 1204 ms 99364 KB Output is correct
4 Correct 588 ms 108196 KB Output is correct
5 Correct 788 ms 100036 KB Output is correct
6 Correct 523 ms 99980 KB Output is correct
7 Correct 392 ms 101128 KB Output is correct
8 Correct 920 ms 100492 KB Output is correct
9 Correct 124 ms 100420 KB Output is correct
10 Correct 87 ms 98872 KB Output is correct
11 Correct 81 ms 98868 KB Output is correct
12 Correct 87 ms 98796 KB Output is correct
13 Correct 1177 ms 99420 KB Output is correct
14 Correct 611 ms 99400 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1321 ms 99420 KB Output is correct
2 Correct 98 ms 98844 KB Output is correct
3 Correct 588 ms 99416 KB Output is correct
4 Correct 100 ms 98756 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1383 ms 99124 KB Output is correct
7 Correct 26 ms 3688 KB Output is correct
8 Correct 80 ms 3832 KB Output is correct
9 Correct 43 ms 3816 KB Output is correct
10 Correct 3 ms 716 KB Output is correct
11 Correct 28 ms 6276 KB Output is correct

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 99252 KB Output is correct
2 Correct 243 ms 99140 KB Output is correct
3 Correct 212 ms 99128 KB Output is correct
4 Correct 217 ms 99132 KB Output is correct
5 Correct 212 ms 99140 KB Output is correct
6 Correct 201 ms 99128 KB Output is correct
7 Correct 270 ms 99136 KB Output is correct
8 Correct 115 ms 99132 KB Output is correct
9 Correct 227 ms 99140 KB Output is correct
10 Correct 221 ms 99116 KB Output is correct
11 Correct 224 ms 99012 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 0 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 0 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 0 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 1 ms 332 KB Output is correct
31 Correct 1 ms 332 KB Output is correct
32 Correct 1638 ms 99932 KB Output is correct
33 Correct 1095 ms 100036 KB Output is correct
34 Correct 755 ms 99908 KB Output is correct
35 Correct 247 ms 99448 KB Output is correct
36 Correct 724 ms 99424 KB Output is correct
37 Execution timed out 2001 ms 99396 KB Time limit exceeded
38 Halted 0 ms 0 KB -