oj.uz

Submission #838522

# Submission time Handle Problem Language Result Execution time Memory
838522 2023-08-27T10:27:43 Z thimote75 Toy Train (IOI17_train) C++14
16 / 100
 1312 ms 1692 KB 
#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 |= node == next || 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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 852 KB Output is correct
2 Correct 4 ms 852 KB Output is correct
3 Correct 6 ms 952 KB Output is correct
4 Correct 4 ms 852 KB Output is correct
5 Correct 5 ms 952 KB Output is correct
6 Correct 3 ms 824 KB Output is correct
7 Correct 3 ms 852 KB Output is correct
8 Correct 3 ms 824 KB Output is correct
9 Correct 3 ms 820 KB Output is correct
10 Correct 4 ms 852 KB Output is correct
11 Correct 3 ms 852 KB Output is correct

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 326 ms 1692 KB Output is correct
2 Correct 377 ms 1620 KB Output is correct
3 Correct 411 ms 1684 KB Output is correct
4 Correct 17 ms 1108 KB Output is correct
5 Correct 405 ms 1184 KB Output is correct
6 Correct 1050 ms 1164 KB Output is correct
7 Correct 6 ms 1108 KB Output is correct
8 Correct 160 ms 1136 KB Output is correct
9 Correct 333 ms 1172 KB Output is correct
10 Correct 257 ms 1100 KB Output is correct
11 Correct 305 ms 1064 KB Output is correct
12 Correct 25 ms 1048 KB Output is correct
13 Correct 797 ms 1624 KB Output is correct
14 Correct 1156 ms 1612 KB Output is correct
15 Correct 795 ms 1516 KB Output is correct
16 Correct 1312 ms 1500 KB Output is correct
17 Correct 551 ms 1500 KB Output is correct
18 Correct 626 ms 1364 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 258 ms 1160 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 903 ms 1184 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 852 KB Output is correct
2 Correct 4 ms 852 KB Output is correct
3 Correct 6 ms 952 KB Output is correct
4 Correct 4 ms 852 KB Output is correct
5 Correct 5 ms 952 KB Output is correct
6 Correct 3 ms 824 KB Output is correct
7 Correct 3 ms 852 KB Output is correct
8 Correct 3 ms 824 KB Output is correct
9 Correct 3 ms 820 KB Output is correct
10 Correct 4 ms 852 KB Output is correct
11 Correct 3 ms 852 KB Output is correct
12 Incorrect 0 ms 212 KB 3rd lines differ - on the 9th token, expected: '1', found: '0'
13 Halted 0 ms 0 KB -