oj.uz

Submission #1037634

# Submission time Handle Problem Language Result Execution time Memory
1037634 2024-07-29T06:16:06 Z thinknoexit Toy Train (IOI17_train) C++17
27 / 100
 960 ms 2164 KB 
#include "train.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
namespace Arezou {
	const int N = 5050;
	vector<int> adj[N], rev[N];
	bool ans[N], vis1[N], vis2[N];
	int n, m;
	void dfs1(int v) {
		for (auto& x : adj[v]) {
			if (!vis1[x]) vis1[x] = 1, dfs1(x);
		}
	}
	void dfs2(int v) {
		for (auto& x : rev[v]) {
			if (!vis2[x]) vis2[x] = 1, dfs2(x);
		}
	}
	vector<int> who_wins(vector<int> a, vector<int> r, vector<int>  _U, vector<int> _V) {
		n = a.size();
		m = _U.size();
		for (int i = 0;i < m;i++) {
			adj[_U[i]].push_back(_V[i]);
			rev[_V[i]].push_back(_U[i]);
		}
		for (int i = 0;i < n;i++) {
			if (!r[i]) continue;
			memset(vis1, 0, sizeof vis1);
			memset(vis2, 0, sizeof vis2);
			dfs1(i);
			dfs2(i);
			bool ch = 0;
			for (int j = 0;j < n;j++) if (vis1[j] && vis2[j]) ch = 1;
			if (ch) {
				for (int j = 0;j < n;j++) if (vis2[j]) ans[j] = 1;
			}
		}
		vector<int> _ans(n);
		for (int i = 0;i < n;i++) _ans[i] = ans[i];
		return _ans;
	}
};
namespace Borzou {
	const int N = 5050;
	vector<int> adj[N], rev[N];
	bool ans[N], vis1[N], vis2[N];
	int n, m, r[N];
	void dfs1(int v) {
		for (auto& x : adj[v]) {
			if (!r[x] && !vis1[x]) vis1[x] = 1, dfs1(x);
		}
	}
	void dfs2(int v) {
		for (auto& x : rev[v]) {
			if (!r[x] && !vis2[x]) vis2[x] = 1, dfs2(x);
		}
	}
	vector<int> who_wins(vector<int> a, vector<int> r, vector<int>  _U, vector<int> _V) {
		n = a.size();
		m = _U.size();
		for (int i = 0;i < m;i++) {
			adj[_U[i]].push_back(_V[i]);
			rev[_V[i]].push_back(_U[i]);
		}
		for (int i = 0;i < n;i++) Borzou::r[i] = r[i], ans[i] = 1;
		for (int i = 0;i < n;i++) {
			if (r[i]) continue;
			memset(vis1, 0, sizeof vis1);
			memset(vis2, 0, sizeof vis2);
			dfs1(i);
			dfs2(i);
			for (int j = 0;j < n;j++) if (vis1[j] && vis2[j]) ans[j] = 0;
		}
		for (int i = 0;i < n;i++) {
			for (int j = 0;j < n;j++) {
				for (auto& x : adj[j]) {
					if (!ans[x]) ans[j] = 0;
				}
			}
		}
		vector<int> _ans(n);
		for (int i = 0;i < n;i++) _ans[i] = ans[i];
		return _ans;
	}
};
namespace Linear {
	const int N = 5050;
	vector<int> adj[N];
	int n, m;
	vector<int> who_wins(vector<int> a, vector<int> r, vector<int>  _U, vector<int> _V) {
		n = a.size();
		m = _U.size();
		for (int i = 0;i < m;i++) {
			adj[_U[i]].push_back(_V[i]);
		}
		vector<int> ans(n);
		ans[n - 1] = r[n - 1];
		for (int i = n - 2;i >= 0;i--) {
			if (a[i] == 0) { // Borzou
				bool ch = 0;
				for (auto& x : adj[i]) {
					if (x == i && !r[i]) ch = 1;
					else if (x != i && !ans[x]) ch = 1;
				}
				ans[i] = ch ^ 1;
			}
			else { // Arezou
				bool ch = 0;
				for (auto& x : adj[i]) {
					if (x == i && r[i]) ch = 1;
					else if (x != i && ans[x]) ch = 1;
				}
				ans[i] = ch;
			}
		}
		return ans;
	}
};
vector<int> who_wins(vector<int> a, vector<int> r, vector<int>  _U, vector<int> _V) {
	bool ch = 1;
	for (auto& x : a) ch &= x == 0;
	if (ch) return Borzou::who_wins(a, r, _U, _V);
	ch = 1;
	for (auto& x : a) ch &= x == 1;
	if (ch) return Arezou::who_wins(a, r, _U, _V);
	return Linear::who_wins(a, r, _U, _V);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1368 KB Output is correct
2 Correct 2 ms 1368 KB Output is correct
3 Correct 2 ms 1372 KB Output is correct
4 Correct 2 ms 1384 KB Output is correct
5 Correct 2 ms 1372 KB Output is correct
6 Correct 2 ms 1372 KB Output is correct
7 Correct 48 ms 1644 KB Output is correct
8 Correct 15 ms 1628 KB Output is correct
9 Correct 2 ms 1368 KB Output is correct
10 Correct 2 ms 1372 KB Output is correct
11 Correct 2 ms 1372 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1112 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 40 ms 2164 KB Output is correct
2 Correct 76 ms 2152 KB Output is correct
3 Correct 117 ms 2136 KB Output is correct
4 Correct 435 ms 2088 KB Output is correct
5 Correct 75 ms 1884 KB Output is correct
6 Correct 58 ms 1880 KB Output is correct
7 Correct 461 ms 1884 KB Output is correct
8 Correct 5 ms 1884 KB Output is correct
9 Correct 4 ms 1884 KB Output is correct
10 Correct 7 ms 1988 KB Output is correct
11 Correct 5 ms 1884 KB Output is correct
12 Correct 4 ms 1880 KB Output is correct
13 Correct 5 ms 2000 KB Output is correct
14 Correct 5 ms 1884 KB Output is correct
15 Correct 5 ms 2108 KB Output is correct
16 Correct 5 ms 2140 KB Output is correct
17 Correct 6 ms 1884 KB Output is correct
18 Correct 262 ms 1772 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 1848 KB Output is correct
2 Correct 274 ms 1880 KB Output is correct
3 Correct 313 ms 2032 KB Output is correct
4 Correct 175 ms 1884 KB Output is correct
5 Correct 591 ms 2060 KB Output is correct
6 Correct 551 ms 2056 KB Output is correct
7 Correct 518 ms 1884 KB Output is correct
8 Correct 244 ms 1992 KB Output is correct
9 Correct 100 ms 1884 KB Output is correct
10 Correct 141 ms 1880 KB Output is correct
11 Correct 145 ms 2060 KB Output is correct
12 Correct 143 ms 1884 KB Output is correct
13 Correct 960 ms 2132 KB Output is correct
14 Correct 545 ms 1984 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1624 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 2 ms 1368 KB Output is correct
2 Correct 2 ms 1368 KB Output is correct
3 Correct 2 ms 1372 KB Output is correct
4 Correct 2 ms 1384 KB Output is correct
5 Correct 2 ms 1372 KB Output is correct
6 Correct 2 ms 1372 KB Output is correct
7 Correct 48 ms 1644 KB Output is correct
8 Correct 15 ms 1628 KB Output is correct
9 Correct 2 ms 1368 KB Output is correct
10 Correct 2 ms 1372 KB Output is correct
11 Correct 2 ms 1372 KB Output is correct
12 Incorrect 1 ms 1112 KB 3rd lines differ - on the 2nd token, expected: '1', found: '0'
13 Halted 0 ms 0 KB -