Submission #838516

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
838516	2023-08-27T10:20:49 Z	thimote75	Toy Train (IOI17_train)	C++14	11 / 100	1245 ms	1832 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 node = msk >> 1;
	int type = msk & 1;

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

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

	status[msk] = false;

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

		bool result = dfs(nxt_msk);

		if (charger[node] == 1 && !result && type == 0)
			result |= dfs(nxt_msk + 1);
		
		if (controller[node] == 1 && result) {
			rstatus = true;
			break ;
		}
		if (controller[node] == 0 && !result) {
			rstatus = false;
			break ;
		}
	}

	status[msk] = rstatus;
	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);
		stage += 2;
	}

	return answer;
}

Subtask #1
0 / 5.0

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

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	301 ms	1832 KB	Output is correct
2	Correct	381 ms	1764 KB	Output is correct
3	Correct	393 ms	1700 KB	Output is correct
4	Correct	17 ms	1336 KB	Output is correct
5	Correct	397 ms	1368 KB	Output is correct
6	Correct	994 ms	1376 KB	Output is correct
7	Correct	9 ms	1316 KB	Output is correct
8	Correct	159 ms	1332 KB	Output is correct
9	Correct	322 ms	1364 KB	Output is correct
10	Correct	255 ms	1236 KB	Output is correct
11	Correct	316 ms	1256 KB	Output is correct
12	Correct	26 ms	1108 KB	Output is correct
13	Correct	751 ms	1652 KB	Output is correct
14	Correct	1116 ms	1664 KB	Output is correct
15	Correct	780 ms	1660 KB	Output is correct
16	Correct	1245 ms	1660 KB	Output is correct
17	Correct	534 ms	1644 KB	Output is correct
18	Correct	611 ms	1536 KB	Output is correct