oj.uz

Submission #775975

# Submission time Handle Problem Language Result Execution time Memory
775975 2023-07-07T07:59:42 Z Jomnoi Toy Train (IOI17_train) C++17
27 / 100
 1160 ms 1620 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];
int st[MAX_N];
vector <int> ans;
vector <int> nodes;

bool solve(int u) {
	st[u] = nodes.size();
	nodes.push_back(u);
	bool win = false;
	for (auto v : graph[u]) {
		if (st[v] == -1) win |= (solve(v) ^ (A[u] != A[v]));
		else {
			bool good_cycle = false;
			for (int i = st[v]; i < nodes.size(); i++) {
				if (R[nodes[i]] == 1) good_cycle = true;
			}

			if (good_cycle == true and A[u] == 1) win = true;
			else if (good_cycle == false and A[u] == 0) win = true;
		}
	}
	st[u] = -1;
	nodes.pop_back();
	return win;
}

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

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

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]);
		rgraph[v[i]].push_back(u[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 (N <= 15) {
		for (int s = 0; s < N; s++) ans[s] = solve(s) ^ (A[s] == 0);
	}
	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) == false) continue;

			for (int i = 0; i < N; i++) visited[i] = false;
			dfs4(s);
		}
	}
	return ans;
}

Compilation message

train.cpp: In function 'bool solve(int)':
train.cpp:26:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |    for (int i = st[v]; i < nodes.size(); i++) {
      |                        ~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1108 KB Output is correct
2 Correct 3 ms 1108 KB Output is correct
3 Correct 3 ms 1108 KB Output is correct
4 Correct 3 ms 1108 KB Output is correct
5 Correct 3 ms 1108 KB Output is correct
6 Correct 3 ms 1108 KB Output is correct
7 Correct 3 ms 1108 KB Output is correct
8 Correct 3 ms 1108 KB Output is correct
9 Correct 3 ms 980 KB Output is correct
10 Correct 3 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 124 ms 1620 KB Output is correct
2 Correct 124 ms 1584 KB Output is correct
3 Correct 135 ms 1576 KB Output is correct
4 Correct 92 ms 1532 KB Output is correct
5 Correct 105 ms 1504 KB Output is correct
6 Correct 466 ms 1432 KB Output is correct
7 Correct 154 ms 1404 KB Output is correct
8 Correct 88 ms 1408 KB Output is correct
9 Correct 185 ms 1392 KB Output is correct
10 Correct 73 ms 1384 KB Output is correct
11 Correct 114 ms 1372 KB Output is correct
12 Correct 19 ms 1236 KB Output is correct
13 Correct 376 ms 1548 KB Output is correct
14 Correct 710 ms 1544 KB Output is correct
15 Correct 512 ms 1556 KB Output is correct
16 Correct 16 ms 1364 KB Output is correct
17 Correct 63 ms 1468 KB Output is correct
18 Correct 261 ms 1316 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1236 KB Output is correct
2 Correct 82 ms 1332 KB Output is correct
3 Correct 119 ms 1408 KB Output is correct
4 Correct 87 ms 1424 KB Output is correct
5 Correct 289 ms 1436 KB Output is correct
6 Correct 196 ms 1428 KB Output is correct
7 Correct 198 ms 1484 KB Output is correct
8 Correct 84 ms 1364 KB Output is correct
9 Correct 5 ms 1364 KB Output is correct
10 Correct 6 ms 1364 KB Output is correct
11 Correct 6 ms 1364 KB Output is correct
12 Correct 6 ms 1364 KB Output is correct
13 Correct 461 ms 1492 KB Output is correct
14 Correct 232 ms 1372 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1160 ms 1524 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 4 ms 1108 KB Output is correct
2 Correct 3 ms 1108 KB Output is correct
3 Correct 3 ms 1108 KB Output is correct
4 Correct 3 ms 1108 KB Output is correct
5 Correct 3 ms 1108 KB Output is correct
6 Correct 3 ms 1108 KB Output is correct
7 Correct 3 ms 1108 KB Output is correct
8 Correct 3 ms 1108 KB Output is correct
9 Correct 3 ms 980 KB Output is correct
10 Correct 3 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 -