Submission #1199457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199457		dubabuba	Werewolf (IOI18_werewolf)	C++20	0 / 100	472 ms	87312 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);
		pos[u].ff = timer;
		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) {
	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]));
	}

	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 = " << a << endl;
				#endif
			}
		}
	}

	dfs(cnt - 1);
	#ifdef LOCAL
		for(int x : ord)
			cout << x << ' ';
		cout << endl;
	#endif

	clear();
	for(int i = 0; i < n; i++)
		STL[i].insert(i);

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

				auto it = STL[a].lower_bound(pos[A].ff);
				if(it != STL[a].end() && (*it) < pos[A].ss)
					ret[i] = 1;
				else
					ret[i] = 0;

				#ifdef LOCAL
					cout << "ans " << i << " = " << ret[i] << endl;
				#endif
			}
		}
	}

	// cout << "n = " << n << endl;
	// cout << "size = " << ret.size() << endl;
	return ret;
}

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