oj.uz

답안 #430550

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
430550 2021-06-16T15:42:38 Z rainboy 장난감 기차 (IOI17_train) C++
38 / 100
 2000 ms 105464 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;
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 (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

# 결과 실행 시간 메모리 Grader output
1 Correct 244 ms 98868 KB Output is correct
2 Correct 237 ms 98916 KB Output is correct
3 Correct 231 ms 98976 KB Output is correct
4 Correct 256 ms 99044 KB Output is correct
5 Correct 243 ms 98884 KB Output is correct
6 Correct 227 ms 99032 KB Output is correct
7 Correct 339 ms 98976 KB Output is correct
8 Correct 114 ms 98972 KB Output is correct
9 Correct 224 ms 98976 KB Output is correct
10 Correct 233 ms 98924 KB Output is correct
11 Correct 215 ms 99020 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 272 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 0 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 0 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 332 KB Output is correct

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1678 ms 99648 KB Output is correct
2 Correct 1341 ms 99624 KB Output is correct
3 Correct 1042 ms 99576 KB Output is correct
4 Correct 350 ms 99208 KB Output is correct
5 Correct 975 ms 99200 KB Output is correct
6 Execution timed out 2084 ms 99140 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 99008 KB Output is correct
2 Correct 404 ms 99164 KB Output is correct
3 Correct 1358 ms 99272 KB Output is correct
4 Correct 938 ms 105464 KB Output is correct
5 Correct 814 ms 99612 KB Output is correct
6 Correct 570 ms 99692 KB Output is correct
7 Correct 416 ms 100420 KB Output is correct
8 Correct 1281 ms 99908 KB Output is correct
9 Correct 186 ms 99892 KB Output is correct
10 Correct 84 ms 98812 KB Output is correct
11 Correct 82 ms 98688 KB Output is correct
12 Correct 86 ms 98808 KB Output is correct
13 Correct 1361 ms 99200 KB Output is correct
14 Correct 625 ms 99172 KB Output is correct

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1567 ms 99188 KB Output is correct
2 Correct 94 ms 98756 KB Output is correct
3 Correct 721 ms 99196 KB Output is correct
4 Correct 102 ms 98656 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1310 ms 98968 KB Output is correct
7 Correct 34 ms 3704 KB Output is correct
8 Correct 111 ms 3660 KB Output is correct
9 Correct 50 ms 3660 KB Output is correct
10 Correct 4 ms 716 KB Output is correct
11 Correct 38 ms 6092 KB Output is correct

Subtask #6
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 244 ms 98868 KB Output is correct
2 Correct 237 ms 98916 KB Output is correct
3 Correct 231 ms 98976 KB Output is correct
4 Correct 256 ms 99044 KB Output is correct
5 Correct 243 ms 98884 KB Output is correct
6 Correct 227 ms 99032 KB Output is correct
7 Correct 339 ms 98976 KB Output is correct
8 Correct 114 ms 98972 KB Output is correct
9 Correct 224 ms 98976 KB Output is correct
10 Correct 233 ms 98924 KB Output is correct
11 Correct 215 ms 99020 KB Output is correct
12 Correct 1 ms 272 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 0 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 0 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 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 1678 ms 99648 KB Output is correct
33 Correct 1341 ms 99624 KB Output is correct
34 Correct 1042 ms 99576 KB Output is correct
35 Correct 350 ms 99208 KB Output is correct
36 Correct 975 ms 99200 KB Output is correct
37 Execution timed out 2084 ms 99140 KB Time limit exceeded
38 Halted 0 ms 0 KB -