Submission #789996

#	Time	Username	Problem	Language	Result	Execution time	Memory
789996		Sohsoh84	Toy Train (IOI17_train)	C++17	11 / 100	238 ms	24844 KiB

train

#include "train.h"
#include <bits/stdc++.h>

using namespace std;

#define all(x)		(x).begin(), (x).end()
#define sep		' '
#define debug(x)	cerr << #x << ": " << x << endl;

const int MAXN = 1e6 + 10;

int n, m, col[MAXN];
bool A[MAXN], R[MAXN];
vector<int> adj[MAXN];
bool W[MAXN];

void dfs(int v) {
	col[v] = 1;
	if (R[v]) {
		col[v] = 2;
		return;
	}

	for (int u : adj[v]) {
		if (col[u] == 1) W[v] = 1;
		else if (col[u] == 0) dfs(u);
	}

	col[v] = 2;
}

vector<int> who_wins(vector<int> a_, vector<int> r_, vector<int> u_, vector<int> v_) {
	n = a_.size();
	for (int i = 0; i < n; i++)
		A[i] = a_[i], R[i] = r_[i];
	
	m = u_.size();
	for (int i = 0; i < m; i++)
		adj[u_[i]].push_back(v_[i]);
	
	for (int i = 0; i < n; i++)
		if (!col[i])
			dfs(i);
	
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			for (int u : adj[j])
				W[j] |= W[u];
	

	vector<int> res;
	for (int i = 0; i < n; i++)
		res.push_back(!W[i]);
	return res;
}

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