Submission #789964

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
789964	2023-07-22T08:22:05 Z	ymm	Toy Train (IOI17_train)	C++17	11 / 100	1764 ms	1488 KB

train

#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 = 5050;
vector<int> A[N];
int col[N];
bool charg[N];
int n, m;
bool vis[N];
bool can_reach_self[N];
int win[N];

bool dfs0(int v, int rt)
{
	vis[v] = 1;
	bool ans = col[v]? 0: 1;
	for (int u : A[v]) {
		bool canu;
		if (vis[u])
			canu = u == rt;
		else
			canu = dfs0(u, rt);
		if (col[v])
			ans |= canu;
		else
			ans &= canu;
	}
	return ans;
}

bool dfs1(int v)
{
	vis[v] = 1;
	if (charg[v] && can_reach_self[v]) {
		win[v] = 1;
		return 1;
	}
	bool ans = col[v]? 0: 1;
	for (int u : A[v]) {
		bool wu;
		if (vis[u])
			wu = win[u] == 1;
		else
			wu = dfs1(u);
		if (col[v])
			ans |= wu;
		else
			ans &= wu;
	}
	win[v] = ans;
	return ans;
}

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) {
		memset(vis, 0, sizeof(vis));
		can_reach_self[i] = dfs0(i, i);
	}
	vector<int> ans(n);
	Loop (i,0,n) {
		memset(vis, 0, sizeof(vis));
		memset(win, -1, sizeof(win));
		ans[i] = dfs1(i);
	}
	return ans;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	164 ms	1092 KB	3rd lines differ - on the 26th 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
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	263 ms	1356 KB	Output is correct
2	Correct	243 ms	1336 KB	Output is correct
3	Correct	238 ms	1304 KB	Output is correct
4	Correct	1242 ms	1344 KB	Output is correct
5	Correct	1115 ms	1200 KB	Output is correct
6	Correct	788 ms	1280 KB	Output is correct
7	Correct	361 ms	1252 KB	Output is correct
8	Correct	413 ms	1304 KB	Output is correct
9	Correct	356 ms	1288 KB	Output is correct
10	Correct	530 ms	1212 KB	Output is correct
11	Correct	440 ms	1324 KB	Output is correct
12	Correct	34 ms	1108 KB	Output is correct
13	Correct	1570 ms	1484 KB	Output is correct
14	Correct	1565 ms	1488 KB	Output is correct
15	Correct	1581 ms	1488 KB	Output is correct
16	Correct	1546 ms	1444 KB	Output is correct
17	Correct	1611 ms	1440 KB	Output is correct
18	Correct	380 ms	1212 KB	Output is correct