oj.uz

Submission #1037540

# Submission time Handle Problem Language Result Execution time Memory
1037540 2024-07-29T03:39:32 Z thinknoexit Toy Train (IOI17_train) C++17
11 / 100
 1768 ms 1760 KB 
#include "train.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
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++) ::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;
}
/*
4 5
1 0 1 1
0 0 0 1
0 1
1 1
1 2
2 3
3 3
*/

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 1708 KB Output is correct
2 Correct 208 ms 1624 KB Output is correct
3 Correct 122 ms 1560 KB Output is correct
4 Incorrect 1157 ms 1568 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
5 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 1352 KB Output is correct
2 Correct 276 ms 1580 KB Output is correct
3 Correct 317 ms 1680 KB Output is correct
4 Correct 142 ms 1624 KB Output is correct
5 Correct 673 ms 1708 KB Output is correct
6 Correct 656 ms 1716 KB Output is correct
7 Correct 498 ms 1688 KB Output is correct
8 Correct 267 ms 1668 KB Output is correct
9 Correct 106 ms 1620 KB Output is correct
10 Correct 160 ms 1628 KB Output is correct
11 Correct 157 ms 1704 KB Output is correct
12 Correct 162 ms 1708 KB Output is correct
13 Correct 936 ms 1760 KB Output is correct
14 Correct 556 ms 1624 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1768 ms 1620 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 Incorrect 53 ms 1116 KB 3rd lines differ - on the 14th token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -