Submission #838440

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
838440	2023-08-26T23:46:48 Z	thimote75	Toy Train (IOI17_train)	C++14	11 / 100	1148 ms	1788 KB

train

#include "train.h"
#include <bits/stdc++.h>

using namespace std;

using idata = vector<int>;
using bdata = vector<bool>;
using igrid = vector<idata>;

idata controller, charger;
int N, M;

igrid roads;

idata visited; int stage = 1;
bdata status;

bool dfs (int msk, int depth) {
	int node = msk >> 1;
	int type = msk & 1;

	if (visited[msk] >= stage) return status[msk];
	visited[msk] = stage;

	if (depth != 0 && type == 1 && visited[msk - 1] == stage) {
		status[msk] = true;
		visited[msk] = stage + 1;
		return true;
	}

	status[msk] = false;

	for (int next : roads[node]) {
		int nxt_msk = next * 2 + type;

		if (dfs(nxt_msk, depth + 1)
		 || (
			charger[node] == 1
			&& type == 0
			&& dfs(nxt_msk + 1, 1)
		 )) {
			status[msk] = true;
			visited[msk] = stage + 1;
			return true;
		}
	}

	visited[msk] = stage + 1;
	return status[msk];
}

idata who_wins(idata _controller, idata _charger, idata u, idata v) {
	N = _controller.size(); M = u.size();

	controller = _controller;
	charger    = _charger;

	roads.resize(N);

	for (int i = 0; i < M; i ++)
		roads[u[i]].push_back(v[i]);

	visited.resize(2 * N);
	status .resize(2 * N);

	idata answer(N, false);
	for (int i = 0; i < N; i ++) {
		answer[i] = dfs(2 * i, 1);
		stage += 2;
	}

	return answer;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	3 ms	852 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	212 KB	3rd lines differ - on the 8th token, expected: '0', found: '1'
2	Halted	0 ms	0 KB	-

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	274 ms	1628 KB	Output is correct
2	Correct	351 ms	1748 KB	Output is correct
3	Correct	364 ms	1700 KB	Output is correct
4	Correct	15 ms	1364 KB	Output is correct
5	Correct	372 ms	1392 KB	Output is correct
6	Correct	919 ms	1364 KB	Output is correct
7	Correct	6 ms	1236 KB	Output is correct
8	Correct	152 ms	1344 KB	Output is correct
9	Correct	289 ms	1368 KB	Output is correct
10	Correct	223 ms	1276 KB	Output is correct
11	Correct	289 ms	1236 KB	Output is correct
12	Correct	24 ms	1236 KB	Output is correct
13	Correct	694 ms	1656 KB	Output is correct
14	Correct	1054 ms	1788 KB	Output is correct
15	Correct	729 ms	1664 KB	Output is correct
16	Correct	1148 ms	1656 KB	Output is correct
17	Correct	483 ms	1704 KB	Output is correct
18	Correct	548 ms	1408 KB	Output is correct