Submission #838500

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
838500	2023-08-27T09:55:51 Z	thimote75	Toy Train (IOI17_train)	C++14	11 / 100	1232 ms	1868 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;

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

		bool result = (dfs(nxt_msk, depth + 1)
		 || (
			charger[node] == 1
			&& type == 0
			&& dfs(nxt_msk + 1, 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, 1);
		stage += 2;
	}

	return answer;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	4 ms	852 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	0 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	323 ms	1868 KB	Output is correct
2	Correct	391 ms	1760 KB	Output is correct
3	Correct	388 ms	1696 KB	Output is correct
4	Correct	20 ms	1364 KB	Output is correct
5	Correct	409 ms	1384 KB	Output is correct
6	Correct	1004 ms	1376 KB	Output is correct
7	Correct	7 ms	1236 KB	Output is correct
8	Correct	160 ms	1340 KB	Output is correct
9	Correct	317 ms	1364 KB	Output is correct
10	Correct	244 ms	1276 KB	Output is correct
11	Correct	315 ms	1260 KB	Output is correct
12	Correct	26 ms	1280 KB	Output is correct
13	Correct	746 ms	1660 KB	Output is correct
14	Correct	1122 ms	1668 KB	Output is correct
15	Correct	783 ms	1744 KB	Output is correct
16	Correct	1232 ms	1740 KB	Output is correct
17	Correct	535 ms	1652 KB	Output is correct
18	Correct	602 ms	1408 KB	Output is correct