oj.uz

Submission #775942

# Submission time Handle Problem Language Result Execution time Memory
775942 2023-07-07T07:33:28 Z Jomnoi Toy Train (IOI17_train) C++17
16 / 100
 661 ms 1252 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 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;
}

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 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();
	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 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 724 KB Output is correct
6 Correct 3 ms 724 KB Output is correct
7 Correct 3 ms 724 KB Output is correct
8 Correct 3 ms 772 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 2 ms 724 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 1st 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 111 ms 1252 KB Output is correct
2 Correct 120 ms 1224 KB Output is correct
3 Correct 127 ms 1248 KB Output is correct
4 Correct 87 ms 1228 KB Output is correct
5 Correct 107 ms 1192 KB Output is correct
6 Correct 409 ms 1112 KB Output is correct
7 Correct 139 ms 1084 KB Output is correct
8 Correct 81 ms 1080 KB Output is correct
9 Correct 163 ms 1076 KB Output is correct
10 Correct 67 ms 1056 KB Output is correct
11 Correct 106 ms 980 KB Output is correct
12 Correct 18 ms 1040 KB Output is correct
13 Correct 365 ms 1236 KB Output is correct
14 Correct 661 ms 1228 KB Output is correct
15 Correct 462 ms 1236 KB Output is correct
16 Correct 15 ms 1112 KB Output is correct
17 Correct 56 ms 1152 KB Output is correct
18 Correct 252 ms 1040 KB Output is correct

Subtask #4
0 / 11.0

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

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 305 ms 1204 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 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 724 KB Output is correct
6 Correct 3 ms 724 KB Output is correct
7 Correct 3 ms 724 KB Output is correct
8 Correct 3 ms 772 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Incorrect 0 ms 340 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
13 Halted 0 ms 0 KB -