Submission #977422

#	Time	Username	Problem	Language	Result	Execution time	Memory
977422		mariaclara	Toy Train (IOI17_train)	C++17	100 / 100	674 ms	1624 KiB

train

#include "train.h"
#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> pii;
const int INF = 1e9+10;
const ll LINF = 1e18+10;
#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define mk make_pair
#define pb push_back
#define f first 
#define s second

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
	int n = sz(a), m = sz(u); 
	vector<int> ans(n,1), grau(n);
	vector<vector<int>> edges(n);

	for(int i = 0; i < m; i++) 
		edges[v[i]].pb(u[i]), grau[u[i]]++;

	while(1) {
		bool ok = 0;
		vector<int> at_grau(n);
		vector<bool> vis(n);
		queue<int> fila;

		for(int i = 0; i < n; i++) {
			if(r[i] and ans[i]) fila.push(i);
			at_grau[i] = grau[i];
		}

		while(!fila.empty()) {
			int x = fila.front();
			fila.pop();

			if(vis[x]) continue;
			vis[x] = 1;

			for(int viz : edges[x]) {
				at_grau[viz]--;
				if(at_grau[viz] == 0 or a[viz]) fila.push(viz);
			}
		}

		for(int i = 0; i < n; i++) {
			if(ans[i] and !vis[i]) ok = 1;
			if(!vis[i]) ans[i] = 0, fila.push(i);
			at_grau[i] = grau[i];
			vis[i] = 0;
		}

		while(!fila.empty()) {
			int x = fila.front();
			fila.pop();

			if(vis[x]) continue;
			if(ans[x]) ok = 1;
			vis[x] = 1;
			ans[x] = 0;

			for(int viz : edges[x]) {
				at_grau[viz]--;
				if(at_grau[viz] == 0 or !a[viz]) fila.push(viz);
			}
		}

		if(!ok) break;
	}

	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