제출 #1199467

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1199467		dubabuba	Werewolf (IOI18_werewolf)	C++20	15 / 100	4043 ms	87412 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

#define ff first
#define ss second
#define MP make_pair

typedef vector<int> vi;
typedef pair<int, int> pii;

const int mxn = 4e5 + 10;
int n, m, q, cnt, timer;
int par[mxn], query[mxn];
vi ord, chi[mxn];
set<int> STL[mxn];

void clear() {
	cnt = n;
	timer = 0;
	memset(par, -1, sizeof par);
}

int parent(int u) {
	return par[u] < 0 ? u : par[u] = parent(par[u]);
}

int unite(int u, int v, bool sus = false) {
	u = parent(u);
	v = parent(v);
	if(u == v) return -1;

	if(sus) {
		if(STL[u].size() < STL[v].size())
			swap(STL[u], STL[v]);
		swap(STL[cnt], STL[u]);
		for(int x : STL[v])
			STL[cnt].insert(x);
		STL[v].clear();
	}

	par[u] = cnt;
	par[v] = cnt;
	chi[cnt].push_back(u);
	chi[cnt].push_back(v);
	return (cnt++);
}

pii pos[mxn];
void dfs(int u) {
	pos[u].ff = timer;
	if(u < n) {
		ord.push_back(u);
		timer++;
		pos[u].ss = timer;
		return;
	}

	for(int v : chi[u])
		dfs(v);
	pos[u].ss = timer;
}

vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
	#ifdef LOCAL
		cout << "This is LOCAL\n";
	#endif

	n = N;
	m = X.size();
	q = S.size();

	vector<pii> HQ[n];
	vector<pii> WQ[n];

	for(int i = 0; i < m; i++) {
		int mn = min(X[i], Y[i]);
		int mx = max(X[i], Y[i]);
		HQ[mn].push_back(MP(-1, mx));
		WQ[mx].push_back(MP(-1, mn));
	}

	for(int i = 0; i < q; i++) {
		int l = L[i], r = R[i];
		HQ[l].push_back(MP(i, S[i]));
		WQ[r].push_back(MP(i, E[i]));
	}

	#ifdef LOCAL
		cout << "\nHumans\n";
	#endif
	clear();
	for(int u = n - 1; u >= 0; u--) {
		for(pii p : HQ[u]) {
			int i = p.ff;
			int v = p.ss;

			if(i == -1) {
				int a = unite(u, v);
				#ifdef LOCAL
					cout << "unite 0: " << u << ' ' << v << " --> " << a << endl;
				#endif
			}
			else {
				int a = parent(v);
				query[i] = a;

				#ifdef LOCAL
					cout << " * query " << i << ": " << v << " -> (" << u << ", " << n - 1 << ") = " << a << endl;
				#endif
			}
		}
	}

	// bool vis[2 * n];
	// memset(vis, 0, sizeof vis);
	// for(int i = 0; i < n; i++) {
	// 	int a = parent(i);
	// 	if(vis[a] == 0) {
	// 		dfs(a);
	// 		vis[a] = 1;
	// 	}
	// }
	dfs(cnt - 1);
	#ifdef LOCAL
		for(int x : ord)
			cout << x << ' ';
		cout << endl;
		for(int i = 0; i < cnt; i++) {
			cout << i << ": " << pos[i].ff << ' ' << pos[i].ss << endl;
		}
	#endif

	clear();
	for(int i = 0; i < n; i++) {
		// STL[i].insert(pos[i].ff);
		STL[i].insert(i);
	}

	#ifdef LOCAL
		cout << "\nWolves\n";
	#endif

	vi ret(q);
	for(int u = 0; u < n; u++) {
		for(pii p : WQ[u]) {
			int i = p.ff;
			int v = p.ss;

			if(i == -1) {
				int a = unite(u, v, 1);
				#ifdef LOCAL
					cout << "unite 1: " << u << ' ' << v << " --> " << a << endl;
				#endif
			}
			else {
				int a = parent(v);
				int A = query[i];

				#ifdef LOCAL
					cout << " * ans " << i << " = " << v << " -> (0, " << u << ") = " << ret[i] << endl;
				#endif

				ret[i] = 0;
				for(int j = pos[A].ff; j < pos[A].ss; j++) {
					// cout << ord[i] << ' ';
					if(STL[a].find(ord[j]) != STL[a].end()) {
						ret[i] = 1;
						break;
					}
				}
			}
		}
	}

	return ret;
}
/*
10 9 10
6 7
1 5
8 0
2 9
9 4
2 7
8 5
6 0
3 4
4 9 0 9
8 1 8 9
1 8 1 8
8 3 5 5
8 9 3 9
0 1 0 2
9 0 6 6
1 7 1 8
9 4 5 6
9 5 0 9

*/

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51