제출 #1241581

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1241581		lovrot	Toy Train (IOI17_train)	C++20	0 / 100	595 ms	2116 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], r[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] && !r[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 && !r[v]) { cmp[v] = cmp[u]; cer(v); }
	}
	deb("%d ", u);
}

void dfs(int u, int &val) { 
	if(ans[u]) { 
		val = 1;
		return;
	}

	bio[u] = 1;

	for(int v : g[u]) { 
		if(!bio[v]) { dfs(v, val); }
	}

	return;
}

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;
	}

	for(int i = 0; i < (int) A.size(); ++i) r[i] = R[i];

	memset(bio, 0, sizeof(bio));
	for(int i = 0; i < (int) A.size(); ++i) { 
		if(!r[i] && !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 = 1; i < cnt; ++i) { 
		if((int) c[i].size() >= 2 || self[c[i][0]]) { 
			for(int u : c[i]) { ans[u] = 1; }
		}
	}

	vector<int> res((int) A.size());
	for(int i = 0; i < (int) A.size(); ++i) { memset(bio, 0, sizeof(bio)); dfs(i, res[i]); }
	return res;
}

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