Submission #775975

#	Time	Username	Problem	Language	Result	Execution time	Memory
775975		Jomnoi	Toy Train (IOI17_train)	C++17	27 / 100	1160 ms	1620 KiB

train

#include <bits/stdc++.h>
#include "train.h"
using namespace std;

const int MAX_N = 5005;
const int MAX_M = 20005;

int N, M;
bool ok;
vector <int> graph[MAX_N], rgraph[MAX_N];
int A[MAX_N], R[MAX_N], good[MAX_N];
bool visited[MAX_N];
bool self[MAX_N], nxt[MAX_N];
int st[MAX_N];
vector <int> ans;
vector <int> nodes;

bool solve(int u) {
	st[u] = nodes.size();
	nodes.push_back(u);
	bool win = false;
	for (auto v : graph[u]) {
		if (st[v] == -1) win |= (solve(v) ^ (A[u] != A[v]));
		else {
			bool good_cycle = false;
			for (int i = st[v]; i < nodes.size(); i++) {
				if (R[nodes[i]] == 1) good_cycle = true;
			}

			if (good_cycle == true and A[u] == 1) win = true;
			else if (good_cycle == false and A[u] == 0) win = true;
		}
	}
	st[u] = -1;
	nodes.pop_back();
	return win;
}

bool dfs(int u, int x) {
	visited[u] = true;
	for (auto v : graph[u]) {
		if (v == x) return true;
		if (visited[v] == false and dfs(v, x) == true) return true;
	}
	return false;
}

bool dfs2(int u) {
	visited[u] = true;
	if (R[u] == 1) return true;
	for (auto v : graph[u]) {
		if (visited[v] == false and dfs2(v) == true) return true;
	}
	return false;
}

bool dfs3(int u, int x) {
	visited[u] = true;
	for (auto v : graph[u]) {
		if (v == x) return true;
		if (visited[v] == false and R[v] == 0 and dfs3(v, x) == true) return true;
	}
	return false;
}

void dfs4(int v) {
	visited[v] = true;
	ans[v] = 0;
	for (auto u : rgraph[v]) {
		if (visited[u] == false) dfs4(u);
	}
}

vector <int> who_wins(vector <int> a, vector <int> r, vector <int> u, vector <int> v) {
	N = a.size(), M = u.size();
	bool all_1 = true, sub1 = true;
	for (int i = 0; i < N; i++) {
		A[i] = a[i], R[i] = r[i];

		if (A[i] == 0) all_1 = false;
	}
	for (int i = 0; i < M; i++) {
		if (u[i] != v[i] and u[i] != v[i] - 1) sub1 = false;
		if (u[i] == v[i]) self[u[i]] = true;
		else if (u[i] + 1 == v[i]) nxt[u[i]] = true;

		graph[u[i]].push_back(v[i]);
		rgraph[v[i]].push_back(u[i]);
	}

	ans = vector <int> (N, 0);
	if (sub1 == true) {
		ok = R[N - 1];
		for (int i = N - 1; i >= 0; i--) {
			if (self[i] == true) {
				if (R[i] == 1 and A[i] == 1) ok = true;
				else if (R[i] == 0 and A[i] == 0) ok = false;
			}
			
			ans[i] = ok;

			if (i > 0 and nxt[i - 1] == false) ok = R[i - 1];
		}
	}
	else if (N <= 15) {
		for (int s = 0; s < N; s++) ans[s] = solve(s) ^ (A[s] == 0);
	}
	else if (all_1 == true) {
		for (int s = 0; s < N; s++) {
			if (R[s] == 0) continue;
			for (int i = 0; i < N; i++) visited[i] = false;

			if (dfs(s, s) == false) R[s] = 0;
		}
		for (int s = 0; s < N; s++) {
			for (int i = 0; i < N; i++) visited[i] = false;

			ans[s] = dfs2(s);
		}
	}
	else {
		ans = vector <int> (N, 1);
		for (int s = 0; s < N; s++) {
			if (R[s] == 1) continue;
			for (int i = 0; i < N; i++) visited[i] = false;

			if (dfs3(s, s) == false) continue;

			for (int i = 0; i < N; i++) visited[i] = false;
			dfs4(s);
		}
	}
	return ans;
}

Compilation message (stderr)

train.cpp: In function 'bool solve(int)':
train.cpp:26:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |    for (int i = st[v]; i < nodes.size(); i++) {
      |                        ~~^~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 0 / 12
• Subtask 6: 0 / 51