oj.uz

Submission #775944

# Submission time Handle Problem Language Result Execution time Memory
775944 2023-07-07T07:35:50 Z Jomnoi Toy Train (IOI17_train) C++17
16 / 100
 707 ms 1504 KB 
#include <bits/stdc++.h>
#include "train.h"
using namespace std;

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

int N, M;
bool ok;
vector <int> graph[MAX_N];
int A[MAX_N], R[MAX_N], good[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 dfs3(int u, int x) {
	visited[u] = true;
	for (auto v : graph[u]) {
		if (v == x) return true;
		if (visited[v] == false and R[v] == 0 and dfs3(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;
}

bool dfs4(int u) {
	visited[u] = true;
	if (good[u] == 1) return true;
	for (auto v : graph[u]) {
		if (visited[v] == false and R[v] == 0 and dfs4(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();
	bool all_1 = true, sub1 = true;
	for (int i = 0; i < N; i++) {
		A[i] = a[i], R[i] = r[i];

		if (A[i] == 0) all_1 = false;
	}
	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) {
		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 if (all_1 == true) {
		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);
		}
	}
	else {
		for (int s = 0; s < N; s++) {
			if (R[s] == 1) continue;
			for (int i = 0; i < N; i++) visited[i] = false;

			if (dfs3(s, s) == true) good[s] = 1;
		}
		for (int s = 0; s < N; s++) {
			for (int i = 0; i < N; i++) visited[i] = false;

			ans[s] = !dfs4(s);
		}
	}
	return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 852 KB Output is correct
2 Correct 4 ms 852 KB Output is correct
3 Correct 3 ms 852 KB Output is correct
4 Correct 3 ms 828 KB Output is correct
5 Correct 4 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 4 ms 844 KB Output is correct
11 Correct 3 ms 828 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB 3rd lines differ - on the 2nd 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 120 ms 1384 KB Output is correct
2 Correct 146 ms 1352 KB Output is correct
3 Correct 139 ms 1364 KB Output is correct
4 Correct 94 ms 1348 KB Output is correct
5 Correct 114 ms 1308 KB Output is correct
6 Correct 448 ms 1248 KB Output is correct
7 Correct 155 ms 1212 KB Output is correct
8 Correct 95 ms 1232 KB Output is correct
9 Correct 174 ms 1116 KB Output is correct
10 Correct 83 ms 1188 KB Output is correct
11 Correct 130 ms 1236 KB Output is correct
12 Correct 19 ms 1164 KB Output is correct
13 Correct 422 ms 1440 KB Output is correct
14 Correct 707 ms 1440 KB Output is correct
15 Correct 490 ms 1444 KB Output is correct
16 Correct 16 ms 1324 KB Output is correct
17 Correct 59 ms 1364 KB Output is correct
18 Correct 250 ms 1164 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1108 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 334 ms 1504 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 3 ms 852 KB Output is correct
2 Correct 4 ms 852 KB Output is correct
3 Correct 3 ms 852 KB Output is correct
4 Correct 3 ms 828 KB Output is correct
5 Correct 4 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 4 ms 844 KB Output is correct
11 Correct 3 ms 828 KB Output is correct
12 Incorrect 1 ms 340 KB 3rd lines differ - on the 2nd token, expected: '1', found: '0'
13 Halted 0 ms 0 KB -