Submission #76236

#	Time	Username	Problem	Language	Result	Execution time	Memory
76236		khsoo01	Werewolf (IOI18_werewolf)	C++11	100 / 100	1290 ms	123464 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
#define X first
#define Y second

using namespace std;
typedef pair<int, int> pii;

const int N = 200005, M = 400005, F = 262144, G = 19, inf = 1e9;

int n, m, q, its[N];

vector<pii> edg;

struct event {
	int p, l, r, v, i;
	bool operator < (const event &T) const {
		return p < T.p;
	}
};

vector<event> swp;

struct disjoint_set {
	int par[2*N];
	void init (int X) {
		for(int i=1;i<=X;i++) {
			par[i] = i;
		}
	}
	int Find (int X) {
		if(par[X] == X) return X;
		return par[X] = Find(par[X]);
	}
	int Union (int X, int Y) {
		X = Find(X);
		Y = Find(Y);
		par[Y] = X;
		return Y;
	}
};

struct connectivity_tree {
	int par[G][2*N], inv[N], ord[N], s[2*N], e[2*N], v[2*N], l[2*N], r[2*N], cc, oc;
	disjoint_set dsj;
	void init (int V) {
		dsj.init(2*n);
		cc = n;
		v[0] = inf;
		for(int i=1;i<=n;i++) {
			v[i] = V;
		}
	}
	void build () {
		for(int i=1;i<G;i++) {
			for(int j=1;j<=cc;j++) {
				par[i][j] = par[i-1][par[i-1][j]];
			}
		}
	}
	void connect (int A, int B, int C) {
		if(dsj.Find(A) == dsj.Find(B)) return;
		++cc;
		int X = dsj.Union(cc, A);
		int Y = dsj.Union(cc, B);
		par[0][X] = cc;
		par[0][Y] = cc;
		l[cc] = X;
		r[cc] = Y;
		v[cc] = C;
	}
	void trav (int I) {
		if(I <= n) {
			oc++;
			s[I] = oc;
			e[I] = oc;
			ord[oc] = I;
			inv[I] = oc;
		}
		else {
			trav(l[I]);
			trav(r[I]);
			s[I] = s[l[I]];
			e[I] = e[r[I]];
		}
	}
	void trav () {trav(cc);}
	pii get (int I, int V) {
		for(int i=G;i--;) {
			if(v[par[i][I]] <= V) I = par[i][I];
		}
		return {s[I], e[I]};
	}
} a, b;

struct segment_tree {
	int v[2*F];
	void upd (int P, int V) {
		P += F;
		while(P) {
			v[P] += V;
			P /= 2;
		}
	}
	int get (int S, int E) {
		S += F;
		E += F;
		int R = 0;
		while(S <= E) {
			if(S%2 == 1) R += v[S++];
			if(E%2 == 0) R += v[E--];
			S /= 2;
			E /= 2;
		}
		return R;
	}
} seg;

vector<int> check_validity(int _N, vector<int> _X, vector<int> _Y, vector<int> _S, vector<int> _E, vector<int> _L, vector<int> _R) {
	n = _N;
	m = (int)_X.size();
	q = (int)_L.size();
	a.init(-n);
	b.init(0);
	for(int i=0;i<m;i++) {
		int A = _X[i]+1, B = _Y[i]+1;
		if(A > B) swap(A, B);
		edg.push_back({A, B});
	}
	sort(edg.begin(), edg.end());
	reverse(edg.begin(), edg.end());
	for(int i=0;i<m;i++) {
		a.connect(edg[i].X, edg[i].Y, -edg[i].X);
	}
	a.build();
	a.trav();
	for(int i=0;i<m;i++) {
		swap(edg[i].X, edg[i].Y);
	}
	sort(edg.begin(), edg.end());
	for(int i=0;i<m;i++) {
		b.connect(edg[i].X, edg[i].Y, edg[i].X);
	}
	b.build();
	b.trav();
	for(int i=0;i<q;i++) {
		int S, E, X, Y;
		tie(S, E) = a.get(_S[i]+1, -_L[i]-1);
		tie(X, Y) = b.get(_E[i]+1, _R[i]+1);
		swp.push_back({E, X, Y, 1, i});
		swp.push_back({S-1, X, Y, -1, i});
	}
	sort(swp.begin(), swp.end());
	int Z = 0;
	for(auto &E : swp) {
		while(Z < E.p) {
			seg.upd(b.inv[a.ord[++Z]], 1);
		}
		its[E.i] += E.v * seg.get(E.l, E.r);
	}
	vector<int> ans;
	for(int i=0;i<q;i++) {
		ans.push_back(its[i] > 0);
	}
	return ans;
}

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