Submission #790004

#	Time	Username	Problem	Language	Result	Execution time	Memory
790004		Sohsoh84	Toy Train (IOI17_train)	C++17	11 / 100	279 ms	52488 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], c;
bool A[MAXN], R[MAXN];
vector<int> adj[MAXN], adj_r[MAXN];
bool W[MAXN], in_edge[MAXN], WC[MAXN];

vector<int> ord;

void dfs(int v) {
	col[v] = 1;
	for (int u : adj[v])
		if (!col[u])
			dfs(u);

	ord.push_back(v);
}

void sfd(int v) {
	col[v] = c;
	for (int u : adj_r[v])
		if (!col[u])
			sfd(u);
}

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]), adj_r[v_[i]].push_back(u_[i]);
	
	for (int i = 0; i < n; i++)
		if (!col[i])
			dfs(i);	

	
	memset(col, 0, sizeof col);
	reverse(all(ord));
	for (int e : ord) {
		if (!col[e]) {
			c++;
			sfd(e);
		}
	}

	for (int u = 0; u < n; u++)
		for (int v : adj[u])
			if (col[u] == col[v])
				in_edge[col[u]] = true;

	for (int u = 0; u < n; u++)
		if (in_edge[col[u]] && R[u])
			WC[col[u]] = true;

	for (int i = 0; i < n; i++)
		for (int v = 0; v < n; v++)
			for (int u : adj[v])
				WC[col[v]] |= WC[col[u]];

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

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