Submission #403927

#	Time	Username	Problem	Language	Result	Execution time	Memory
403927		LucaDantas	Toy Train (IOI17_train)	C++17	100 / 100	1400 ms	2884 KiB

train

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

#define pb push_back
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a.size())

constexpr int maxn = 5010;

int a[maxn], ligado[maxn], comp[maxn], brabo[maxn], grau[maxn], atv[maxn], cor[maxn];
int n, m, t;

bool mark[maxn];

vector<int> g[maxn], g_rev[maxn], meus[maxn], g_comp[maxn], g_rev_comp[maxn], ord;

void dfs(int u) {
	mark[u] = 1;
	for(int v : g[u])
		if(a[v] && !mark[v]) dfs(v);
	ord.pb(u);
}

void go(int u, int& ok) {
	ok |= ligado[u]<<1;
	comp[u] = t;
	meus[t].pb(u);
	for(int v : g_rev[u]) {
		if(!comp[v] && a[v]) go(v, ok);
		else if(comp[v] == comp[u] && a[v]) ok |= 1;
	}
}

void limpar(int u) {
	brabo[u] = 1, mark[u] = 1;
	for(int v : g_rev_comp[u])
		if(!mark[v] && !cor[v]) limpar(v);
}

vector<int> who_wins(vector<int> A, vector<int> R, vector<int> U, vector<int> V) {
	n = (int)(A.size()), m = (int)(U.size());
	
	for(int i = 0; i < n; i++)
		a[i] = A[i], ligado[i] = R[i];
	
	for(int i = 0; i < m; i++)
		g[U[i]].pb(V[i]), g_rev[V[i]].pb(U[i]);
	
	for(int i = 0; i < n; i++)
		if(a[i] && !mark[i]) dfs(i);
	
	reverse(all(ord));
	for(int i = 0; i < sz(ord); i++) {
		if(comp[ord[i]]) continue;
		int ok = 0; ++t;
		go(ord[i], ok);
		if(ok == 3) brabo[t] = 1;
		if(ok&2) atv[t] = 1;
	}

	for(int i = 0; i < n; i++)
		if(!a[i]) comp[i] = ++t, cor[t] = 1, atv[t] = R[i], meus[t] = {i};

	memset(mark, 0, sizeof mark);
	for(int i = 1; i <= t; i++) {
		for(int u : meus[i])
			for(int v : g[u])
				if(!mark[comp[v]])
					mark[comp[v]] = 1, g_comp[i].pb(comp[v]), g_rev_comp[comp[v]].pb(i);
		for(int x : g_comp[i])
			mark[x] = 0;
	}

	memset(mark, 0, sizeof mark);
	for(int i = 1; i <= t; i++)
		if(brabo[i] && !mark[i]) limpar(i);

	for(int rep = 0; rep < n; rep++) {
		vector<int> fontes;

		memset(mark, 0, sizeof mark);
		for(int i = 1; i <= t; i++)
			if(atv[i]) mark[i] = 1, fontes.pb(i);

		for(int i = 1; i <= t; i++)
			grau[i] = sz(g_comp[i]);
		
		while(fontes.size()) {
			int u = fontes.back(); fontes.pop_back();
			for(int v : g_rev_comp[u]) {
				if(mark[v]) continue;
				--grau[v];
				if(!grau[v] || !cor[v]) fontes.pb(v), mark[v] = 1;
			}
		}

		for(int i = 1; i <= t; i++) {
			grau[i] = sz(g_comp[i]);
			if(!mark[i] && !brabo[i]) fontes.pb(i);
		}

		memset(mark, 0, sizeof mark);

		for(int x : fontes)
			mark[x] = 1;

		while(fontes.size()) {
			int u = fontes.back(); fontes.pop_back();
			for(int v : g_rev_comp[u]) {
				if(mark[v]) continue;
				--grau[v];
				if((!grau[v] && !brabo[v]) || cor[v]) fontes.pb(v), mark[v] = 1;
			}
		}

		for(int i = 1; i <= t; i++)
			atv[i] &= !mark[i];
	}

	vector<int> ans(n);

	for(int i = 0; i < n; i++)
		ans[i] = !mark[comp[i]];

	return ans;	
}

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