Submission #1104139

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104139		dubabuba	Werewolf (IOI18_werewolf)	C++14	0 / 100	224 ms	40964 KiB

werewolf

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

using namespace std;

template<typename T, typename U>
void miner(T &MIN, U CMP) { if(MIN > CMP) MIN = CMP; }
template<typename T, typename U>
void maxer(T &MAX, U CMP) { if(MAX < CMP) MAX = CMP; }

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

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

const int inf = 1e9 + 10;
const int mxn = 2e5 + 10;
const int MXN = 4e5 + 10;

int LQ[mxn], RQ[mxn];
int mx[MXN], mn[MXN];
int n, m, q;

int parent(int u, vi &par) {
	if(par[u] < 0) return u;
	return par[u] = parent(par[u], par);
}

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<pair<pii, int>> LE, RE;
	for(int i = 0; i < m; i++) {
		int u = X[i];
		int v = Y[i];
		if(u > v) swap(u, v);
		LE.push_back(MP(MP(u, inf), v));
		RE.push_back(MP(MP(v, -inf), u));
	}

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

	sort(LE.begin(), LE.end(), [&](auto L, auto R) { return L > R; });
	sort(RE.begin(), RE.end());
	int cur = n;

	vi L_anc(2 * n, -1);
	for(int i = 0; i < n; i++)
		mn[i] = i;

	for(auto e : LE) {
		int id = e.ff.ss;
		int u = parent(e.ff.ff, L_anc);
		int v = parent(e.ss, L_anc);
		
		if(id != inf) {
			LQ[id] = mn[v];
			continue;
		}

		if(u == v) continue;

		L_anc[u] = cur;
		L_anc[v] = cur;
		mn[cur] = e.ff.ff;
		miner(mn[cur], mn[u]);
		miner(mn[cur], mn[v]);

		// cout << e.ff.ff << ' ' << e.ss << " -> "
		// 	<< u << ' ' << v << " = "
		// 	<< cur << ": " << mn[cur] << endl;

		cur++;
	}
	mn[cur] = -inf;
	assert(cur == 2 * n - 1);

	// cout << "----------------\n";
	cur = n;
	vi R_anc(2 * n, -1);
	for(int i = 0; i < n; i++)
		mx[i] = i;

	for(auto e : RE) {
		int id = e.ff.ss;
		int u = parent(e.ff.ff, R_anc);
		int v = parent(e.ss, R_anc);
		
		if(id != -inf) {
			RQ[id] = mx[v];
			continue;
		}

		if(u == v) continue;

		R_anc[u] = cur;
		R_anc[v] = cur;
		mx[cur] = e.ff.ff;
		maxer(mx[cur], mx[u]);
		maxer(mx[cur], mx[v]);

		// cout << e.ff.ff << ' ' << e.ss << " -> "
		// 	<< u << ' ' << v << " = "
		// 	<< cur << ": " << mx[cur] << endl;

		cur++;
	}
	mx[cur] = inf;
	assert(cur == 2 * n - 1);

	vi par(n, -1);
	for(int i = 0; i < m; i++) {
		int u = parent(X[i], par);
		int v = parent(Y[i], par);
		if(u == v) continue;

		par[u] += par[v];
		par[v] = u;
	}

	vector<int> ans;
	for(int i = 0; i < q; i++) {
		int l = L[i], r = R[i];
		if(RQ[i] < l || r < LQ[i]) {
			ans.push_back(0);
			continue;
		}

		int SL = parent(LQ[i], par);
		int SR = parent(RQ[i], par);
		if(SL == SR)
			ans.push_back(1);
		else
			ans.push_back(0);
	}

	return ans;
}

/*
6 6 3

5 1
1 2
1 3
3 4
3 0
5 2

4 2 1 2
4 2 2 2
5 4 3 4
*/

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