oj.uz

Submission #775902

# Submission time Handle Problem Language Result Execution time Memory
775902 2023-07-07T06:28:45 Z Jomnoi Toy Train (IOI17_train) C++17
16 / 100
 703 ms 1436 KB 
#include <bits/stdc++.h>
#include "train.h"
using namespace std;

const int MAX_N = 5005;
const int MAX_M = 20005;

int N, M;
vector <int> graph[MAX_N];
int A[MAX_N], R[MAX_N];
bool visited[MAX_N];
bool self[MAX_N], nxt[MAX_N];

bool dfs(int u, int x) {
	visited[u] = true;
	for (auto v : graph[u]) {
		if (v == x) return true;
		if (visited[v] == false and dfs(v, x) == true) return true;
	}
	return false;
}

bool dfs2(int u) {
	visited[u] = true;
	if (R[u] == 1) return true;
	for (auto v : graph[u]) {
		if (visited[v] == false and dfs2(v) == true) return true;
	}
	return false;
}

vector <int> who_wins(vector <int> a, vector <int> r, vector <int> u, vector <int> v) {
	N = a.size(), M = u.size();
	for (int i = 0; i < N; i++) A[i] = a[i], R[i] = r[i];
	bool sub1 = true;
	for (int i = 0; i < M; i++) {
		if (u[i] != v[i] and u[i] != v[i] - 1) sub1 = false;
		if (u[i] == v[i]) self[u[i]] = true;
		else if (u[i] + 1 == v[i]) nxt[u[i]] = true;

		graph[u[i]].push_back(v[i]);
	}

	vector <int> ans(N, 0);
	if (sub1 == true) {
		bool ok = R[N - 1];
		for (int i = N - 1; i >= 0; i--) {
			if (self[i] == true) {
				if (R[i] == 1 and A[i] == 1) ok = true;
				else if (R[i] == 0 and A[i] == 0) ok = false;
			}
			
			ans[i] = ok;

			if (i > 0 and nxt[i - 1] == false) ok = R[i - 1];
		}
	}
	else {
		for (int s = 0; s < N; s++) {
			if (R[s] == 0) continue;
			for (int i = 0; i < N; i++) visited[i] = false;

			if (dfs(s, s) == false) R[s] = 0;
		}
		for (int s = 0; s < N; s++) {
			for (int i = 0; i < N; i++) visited[i] = false;

			ans[s] = dfs2(s);
		}
	}
	return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 724 KB Output is correct
2 Correct 3 ms 724 KB Output is correct
3 Correct 3 ms 724 KB Output is correct
4 Correct 3 ms 724 KB Output is correct
5 Correct 3 ms 852 KB Output is correct
6 Correct 3 ms 852 KB Output is correct
7 Correct 3 ms 852 KB Output is correct
8 Correct 3 ms 852 KB Output is correct
9 Correct 3 ms 852 KB Output is correct
10 Correct 3 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 340 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 143 ms 1240 KB Output is correct
2 Correct 127 ms 1248 KB Output is correct
3 Correct 133 ms 1236 KB Output is correct
4 Correct 85 ms 1204 KB Output is correct
5 Correct 107 ms 1380 KB Output is correct
6 Correct 449 ms 1308 KB Output is correct
7 Correct 142 ms 1280 KB Output is correct
8 Correct 96 ms 1284 KB Output is correct
9 Correct 196 ms 1272 KB Output is correct
10 Correct 70 ms 1236 KB Output is correct
11 Correct 121 ms 1224 KB Output is correct
12 Correct 20 ms 1216 KB Output is correct
13 Correct 403 ms 1432 KB Output is correct
14 Correct 703 ms 1436 KB Output is correct
15 Correct 465 ms 1436 KB Output is correct
16 Correct 19 ms 1320 KB Output is correct
17 Correct 56 ms 1364 KB Output is correct
18 Correct 253 ms 1164 KB Output is correct

Subtask #4
0 / 11.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 51.0

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