oj.uz

Submission #430544

# Submission time Handle Problem Language Result Execution time Memory
430544 2021-06-16T15:37:02 Z rainboy Toy Train (IOI17_train) C++
38 / 100
 2000 ms 105628 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;
	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: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:41:27: warning: unused variable 'j' [-Wunused-variable]
   41 |  int m = uu.size(), h, i, j, t;
      |                           ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 98972 KB Output is correct
2 Correct 239 ms 99068 KB Output is correct
3 Correct 229 ms 98976 KB Output is correct
4 Correct 237 ms 98972 KB Output is correct
5 Correct 243 ms 99076 KB Output is correct
6 Correct 227 ms 98984 KB Output is correct
7 Correct 320 ms 98976 KB Output is correct
8 Correct 114 ms 99028 KB Output is correct
9 Correct 232 ms 98884 KB Output is correct
10 Correct 224 ms 98960 KB Output is correct
11 Correct 219 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 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 288 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 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 288 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1679 ms 99524 KB Output is correct
2 Correct 1270 ms 99608 KB Output is correct
3 Correct 995 ms 99628 KB Output is correct
4 Correct 351 ms 99284 KB Output is correct
5 Correct 953 ms 99272 KB Output is correct
6 Execution timed out 2045 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 85 ms 99136 KB Output is correct
2 Correct 413 ms 99212 KB Output is correct
3 Correct 1382 ms 99520 KB Output is correct
4 Correct 927 ms 105628 KB Output is correct
5 Correct 810 ms 99700 KB Output is correct
6 Correct 561 ms 99780 KB Output is correct
7 Correct 432 ms 100548 KB Output is correct
8 Correct 1256 ms 100016 KB Output is correct
9 Correct 185 ms 99988 KB Output is correct
10 Correct 87 ms 98856 KB Output is correct
11 Correct 82 ms 98820 KB Output is correct
12 Correct 90 ms 98876 KB Output is correct
13 Correct 1360 ms 99280 KB Output is correct
14 Correct 631 ms 99268 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1474 ms 99260 KB Output is correct
2 Correct 92 ms 99040 KB Output is correct
3 Correct 698 ms 99516 KB Output is correct
4 Correct 94 ms 99012 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1270 ms 99052 KB Output is correct
7 Correct 34 ms 3804 KB Output is correct
8 Correct 110 ms 3916 KB Output is correct
9 Correct 49 ms 3916 KB Output is correct
10 Correct 4 ms 820 KB Output is correct
11 Correct 33 ms 6348 KB Output is correct

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 98972 KB Output is correct
2 Correct 239 ms 99068 KB Output is correct
3 Correct 229 ms 98976 KB Output is correct
4 Correct 237 ms 98972 KB Output is correct
5 Correct 243 ms 99076 KB Output is correct
6 Correct 227 ms 98984 KB Output is correct
7 Correct 320 ms 98976 KB Output is correct
8 Correct 114 ms 99028 KB Output is correct
9 Correct 232 ms 98884 KB Output is correct
10 Correct 224 ms 98960 KB Output is correct
11 Correct 219 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 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 288 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 1 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 0 ms 332 KB Output is correct
30 Correct 1 ms 332 KB Output is correct
31 Correct 1 ms 288 KB Output is correct
32 Correct 1679 ms 99524 KB Output is correct
33 Correct 1270 ms 99608 KB Output is correct
34 Correct 995 ms 99628 KB Output is correct
35 Correct 351 ms 99284 KB Output is correct
36 Correct 953 ms 99272 KB Output is correct
37 Execution timed out 2045 ms 99396 KB Time limit exceeded
38 Halted 0 ms 0 KB -