oj.uz

Submission #775948

# Submission time Handle Problem Language Result Execution time Memory
775948 2023-07-07T07:39:01 Z Jomnoi Toy Train (IOI17_train) C++17
16 / 100
 667 ms 1580 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 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;
}

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;

			if (dfs3(s, s) == true) dfs4(s);
		}
	}
	return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 980 KB Output is correct
2 Correct 3 ms 972 KB Output is correct
3 Correct 3 ms 940 KB Output is correct
4 Correct 3 ms 940 KB Output is correct
5 Correct 3 ms 1024 KB Output is correct
6 Correct 3 ms 980 KB Output is correct
7 Correct 3 ms 940 KB Output is correct
8 Correct 3 ms 980 KB Output is correct
9 Correct 3 ms 980 KB Output is correct
10 Correct 4 ms 980 KB Output is correct
11 Correct 3 ms 980 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 116 ms 1580 KB Output is correct
2 Correct 114 ms 1492 KB Output is correct
3 Correct 127 ms 1552 KB Output is correct
4 Correct 84 ms 1552 KB Output is correct
5 Correct 102 ms 1456 KB Output is correct
6 Correct 447 ms 1436 KB Output is correct
7 Correct 131 ms 1364 KB Output is correct
8 Correct 84 ms 1416 KB Output is correct
9 Correct 164 ms 1400 KB Output is correct
10 Correct 68 ms 1364 KB Output is correct
11 Correct 110 ms 1352 KB Output is correct
12 Correct 20 ms 1364 KB Output is correct
13 Correct 366 ms 1556 KB Output is correct
14 Correct 667 ms 1556 KB Output is correct
15 Correct 462 ms 1564 KB Output is correct
16 Correct 17 ms 1440 KB Output is correct
17 Correct 58 ms 1472 KB Output is correct
18 Correct 281 ms 1276 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1236 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 328 ms 1544 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 980 KB Output is correct
2 Correct 3 ms 972 KB Output is correct
3 Correct 3 ms 940 KB Output is correct
4 Correct 3 ms 940 KB Output is correct
5 Correct 3 ms 1024 KB Output is correct
6 Correct 3 ms 980 KB Output is correct
7 Correct 3 ms 940 KB Output is correct
8 Correct 3 ms 980 KB Output is correct
9 Correct 3 ms 980 KB Output is correct
10 Correct 4 ms 980 KB Output is correct
11 Correct 3 ms 980 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 -