oj.uz

Submission #790031

# Submission time Handle Problem Language Result Execution time Memory
790031 2023-07-22T09:30:47 Z ymm Toy Train (IOI17_train) C++17
11 / 100
 1026 ms 1312 KB 
#include "train.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (long long x = (l); x < (r); ++x)
typedef long long ll;
typedef std::pair<ll,ll> pll;
using namespace std;

const int N = 5032;
vector<int> A[N];
bool vis[N];
bool reach_self[N];
bool col[N], charg[N];
int n, m;

bool dfs(int v, int rt)
{
	vis[v] = 1;
	for (int u : A[v]) {
		if (charg[u])
			continue;
		if (u == rt)
			return 1;
		if (vis[u])
			continue;
		if (dfs(u, rt))
			return 1;
	}
	return 0;
}

void dfs2(int v)
{
	vis[v] = 1;
	for (int u : A[v]) {
		if (!vis[u])
			dfs2(u);
	}
}

std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> V, std::vector<int> U) {
	n = a.size();
	m = V.size();
	Loop (i,0,n) {
		col[i] = a[i];
		charg[i] = r[i];
	}
	Loop (i,0,m) {
		int v = V[i], u = U[i];
		A[v].push_back(u);
	}
	Loop (i,0,n) {
		if (charg[i])
			continue;
		memset(vis, 0, sizeof(vis));
		reach_self[i] = dfs(i, i);
	}
	vector<int> ans(n);
	Loop (i,0,n) {
		memset(vis, 0, sizeof(vis));
		dfs2(i);
		Loop (j,0,n)
			ans[i] |= vis[j] && reach_self[j];
		ans[i] = !ans[i];
	}
	return ans;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 163 ms 864 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 0 ms 340 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 254 ms 1224 KB Output is correct
2 Correct 224 ms 1156 KB Output is correct
3 Correct 203 ms 1112 KB Output is correct
4 Incorrect 1006 ms 1112 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 583 ms 972 KB Output is correct
2 Correct 219 ms 1152 KB Output is correct
3 Correct 385 ms 1252 KB Output is correct
4 Correct 429 ms 1236 KB Output is correct
5 Correct 517 ms 1260 KB Output is correct
6 Correct 463 ms 1228 KB Output is correct
7 Correct 462 ms 1224 KB Output is correct
8 Correct 340 ms 1312 KB Output is correct
9 Correct 40 ms 1160 KB Output is correct
10 Correct 674 ms 1204 KB Output is correct
11 Correct 684 ms 1304 KB Output is correct
12 Correct 699 ms 1304 KB Output is correct
13 Correct 662 ms 1292 KB Output is correct
14 Correct 390 ms 1200 KB Output is correct

Subtask #5
0 / 12.0

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