oj.uz

Submission #775955

# Submission time Handle Problem Language Result Execution time Memory
775955 2023-07-07T07:43:05 Z Jomnoi Toy Train (IOI17_train) C++17
16 / 100
 761 ms 1368 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], rgraph[MAX_N];
int A[MAX_N], R[MAX_N], good[MAX_N];
bool visited[MAX_N];
bool self[MAX_N], nxt[MAX_N];
vector <int> ans;

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;
}

void dfs3(int u) {
	for (auto v : graph[u]) {
		if (visited[v] == false and R[v] == 0) {
			visited[v] = true;
			dfs3(v);
		}
	}
}

void dfs4(int v) {
	visited[v] = true;
	ans[v] = 0;
	for (auto u : rgraph[v]) {
		if (visited[u] == false) dfs4(u);
	}
}

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]);
	}

	ans = vector <int> (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 {
		ans = vector <int> (N, 1);
		for (int s = 0; s < N; s++) {
			if (R[s] == 1) continue;
			for (int i = 0; i < N; i++) visited[i] = false;

			dfs3(s);
			if (visited[s] == false) continue;

			for (int i = 0; i < N; i++) visited[i] = false;
			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 3 ms 852 KB Output is correct
3 Correct 3 ms 980 KB Output is correct
4 Correct 3 ms 892 KB Output is correct
5 Correct 3 ms 980 KB Output is correct
6 Correct 3 ms 900 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 1 ms 468 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 113 ms 1360 KB Output is correct
2 Correct 115 ms 1340 KB Output is correct
3 Correct 131 ms 1368 KB Output is correct
4 Correct 85 ms 1332 KB Output is correct
5 Correct 97 ms 1304 KB Output is correct
6 Correct 413 ms 1236 KB Output is correct
7 Correct 133 ms 1200 KB Output is correct
8 Correct 80 ms 1208 KB Output is correct
9 Correct 161 ms 1200 KB Output is correct
10 Correct 67 ms 1184 KB Output is correct
11 Correct 106 ms 1152 KB Output is correct
12 Correct 18 ms 1108 KB Output is correct
13 Correct 353 ms 1344 KB Output is correct
14 Correct 636 ms 1344 KB Output is correct
15 Correct 474 ms 1364 KB Output is correct
16 Correct 15 ms 1236 KB Output is correct
17 Correct 57 ms 1268 KB Output is correct
18 Correct 274 ms 1160 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 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 761 ms 1324 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 3 ms 852 KB Output is correct
3 Correct 3 ms 980 KB Output is correct
4 Correct 3 ms 892 KB Output is correct
5 Correct 3 ms 980 KB Output is correct
6 Correct 3 ms 900 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 1 ms 468 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
13 Halted 0 ms 0 KB -