oj.uz

Submission #430556

# Submission time Handle Problem Language Result Execution time Memory
430556 2021-06-16T15:53:37 Z rainboy Toy Train (IOI17_train) C++
38 / 100
 2000 ms 105448 KB 
#include "train.h"
#include <stdlib.h>
 
using namespace std;
 
const int N = 5000;
 
typedef vector<int> vi;
 
int *ej[N], eo[N];
int dd[N][N + 1], out[N], n;
char rr[N];
 
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());
 
	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;
	}
	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 'vi who_wins(vi, vi, vi, vi)':
train.cpp:32:27: warning: unused variable 'j' [-Wunused-variable]
   32 |  int m = uu.size(), h, i, j, t;
      |                           ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 98964 KB Output is correct
2 Correct 248 ms 98960 KB Output is correct
3 Correct 269 ms 98876 KB Output is correct
4 Correct 247 ms 98924 KB Output is correct
5 Correct 235 ms 98912 KB Output is correct
6 Correct 269 ms 98956 KB Output is correct
7 Correct 313 ms 99012 KB Output is correct
8 Correct 120 ms 98948 KB Output is correct
9 Correct 268 ms 99012 KB Output is correct
10 Correct 219 ms 98948 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 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 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 0 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 0 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 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 0 ms 332 KB Output is correct
20 Correct 0 ms 332 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1674 ms 99568 KB Output is correct
2 Correct 1321 ms 99620 KB Output is correct
3 Correct 1062 ms 99560 KB Output is correct
4 Correct 422 ms 99140 KB Output is correct
5 Correct 956 ms 99180 KB Output is correct
6 Execution timed out 2083 ms 99104 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 98992 KB Output is correct
2 Correct 469 ms 99140 KB Output is correct
3 Correct 1437 ms 99324 KB Output is correct
4 Correct 929 ms 105448 KB Output is correct
5 Correct 872 ms 99612 KB Output is correct
6 Correct 549 ms 99648 KB Output is correct
7 Correct 437 ms 100336 KB Output is correct
8 Correct 1238 ms 100028 KB Output is correct
9 Correct 174 ms 99904 KB Output is correct
10 Correct 79 ms 98756 KB Output is correct
11 Correct 92 ms 98704 KB Output is correct
12 Correct 99 ms 98756 KB Output is correct
13 Correct 1345 ms 99184 KB Output is correct
14 Correct 673 ms 99148 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1558 ms 99140 KB Output is correct
2 Correct 100 ms 98756 KB Output is correct
3 Correct 712 ms 99272 KB Output is correct
4 Correct 107 ms 98628 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1272 ms 98952 KB Output is correct
7 Correct 35 ms 3660 KB Output is correct
8 Correct 112 ms 3660 KB Output is correct
9 Correct 60 ms 3696 KB Output is correct
10 Correct 4 ms 716 KB Output is correct
11 Correct 44 ms 6188 KB Output is correct

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 98964 KB Output is correct
2 Correct 248 ms 98960 KB Output is correct
3 Correct 269 ms 98876 KB Output is correct
4 Correct 247 ms 98924 KB Output is correct
5 Correct 235 ms 98912 KB Output is correct
6 Correct 269 ms 98956 KB Output is correct
7 Correct 313 ms 99012 KB Output is correct
8 Correct 120 ms 98948 KB Output is correct
9 Correct 268 ms 99012 KB Output is correct
10 Correct 219 ms 98948 KB Output is correct
11 Correct 219 ms 99012 KB Output is correct
12 Correct 0 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 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 0 ms 332 KB Output is correct
23 Correct 0 ms 332 KB Output is correct
24 Correct 0 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 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 0 ms 332 KB Output is correct
31 Correct 0 ms 332 KB Output is correct
32 Correct 1674 ms 99568 KB Output is correct
33 Correct 1321 ms 99620 KB Output is correct
34 Correct 1062 ms 99560 KB Output is correct
35 Correct 422 ms 99140 KB Output is correct
36 Correct 956 ms 99180 KB Output is correct
37 Execution timed out 2083 ms 99104 KB Time limit exceeded
38 Halted 0 ms 0 KB -