Submission #789964

#	Time	Username	Problem	Language	Result	Execution time	Memory
789964		ymm	Toy Train (IOI17_train)	C++17	11 / 100	1764 ms	1488 KiB

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
• Subtask 2: 0 / 10
• Subtask 3: 11 / 11
• Subtask 4: 0 / 11
• Subtask 5: 0 / 12
• Subtask 6: 0 / 51