Submission #1241569

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241569		lovrot	Toy Train (IOI17_train)	C++20	11 / 100	5 ms	2372 KiB

train

#include "train.h"
#include <vector>
#include <cstring>
#include <algorithm>
#include <cstdio>

#define X first
#define Y second
#define PB push_back
#define deb(...) //fprintf(stderr, __VA_ARGS__)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 5e3 + 10;

int self[N], bio[N], cmp[N], ans[N];
vector<int> g[N], h[N], topo;
vector<int> c[N], cg[N];

void rec(int u) { 
	bio[u] = 1;
	for(int v : g[u]) { 
		if(!bio[v]) { rec(v); }
	}
	topo.PB(u);
}

void cer(int u) { 
	bio[u] = 2;
	c[cmp[u]].PB(u);
	for(int v : h[u]) {
		if(bio[v] == 1) { cmp[v] = cmp[u]; cer(v); }
	}
	deb("%d ", u);
}

void dfs(int u) { 
	bio[u] = 1;
	for(int v : c[u]) { ans[v] = 1; }
	for(int v : cg[u]) { 
		if(!bio[v]) { dfs(v); }
	}
}

vector<int> who_wins(vector<int> A, vector<int> R, vector<int> U, vector<int> V) {
	for(int i = 0; i < (int) U.size(); ++i) { 
		g[U[i]].PB(V[i]);
		h[V[i]].PB(U[i]);

		if(U[i] == V[i]) self[U[i]] = 1;
	}

	memset(bio, 0, sizeof(bio));
	for(int i = 0; i < (int) A.size(); ++i) { 
		if(!bio[i]) { rec(i); }
	}

	reverse(topo.begin(), topo.end());
	int cnt = 1;
	for(int u : topo) { 
		if(bio[u] == 1) { 
			cmp[u] = cnt++;
			cer(u);
			deb("\n");
		}
	}

	for(int i = 0; i < (int) U.size(); ++i) { 
		if(cmp[U[i]] != cmp[V[i]]) { cg[cmp[V[i]]].PB(cmp[U[i]]); }
	}

	memset(bio, 0, sizeof(bio));
	for(int i = 1; i < cnt; ++i) { 
		int r = -1;
		for(int u : c[i]) { 
			if(R[u]) r = u;
		}

		deb("%d %d %d\n", r, (int) c[i].size(), self[r]);
		if(r != -1 && ((int) c[i].size() >= 2 || self[r])) { 
			dfs(i);
		}
	}

	vector<int> res;
	for(int i = 0; i < (int) A.size(); ++i) res.PB(ans[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