제출 #169674

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
169674		dennisstar	늑대인간 (IOI18_werewolf)	C++11	100 / 100	871 ms	94468 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef vector<int> vim;

int N, M, Q; 
vim V[200010];

struct sler {
	int s, l, n, nd;
}sl[200010], er[200010];

struct tree {
	int tp, tp1;
	vim ch[400010];
	int s[400010], e[400010];
	void in(int a, int b) {
		ch[tp].push_back(a); ch[tp].push_back(b); tp++;
	}
	void dfs(int now) {
		s[now]=e[now]=tp1; tp1++;
		for (int i:ch[now]) {
			dfs(i);
			e[now]=max(e[now], e[i]);
		}
	}
}tr1, tr2;

struct Query {
	int x1, x2, y1, y2, n, ans;
}Qu[200010];

int par[200010], im[200010], dep[200010];

void Un1(int a, int b) {
	while (par[a]!=-1) a=par[a];
	while (par[b]!=-1) b=par[b];
	if (a==b) return ;
	if (dep[a]<dep[b]) swap(a, b);
	par[b]=a, dep[a]=max(dep[a], dep[b]+1);
	tr1.in(im[a], im[b]);
	im[a]=tr1.tp-1;
}

void f1() {
	tr1.tp=N, tr1.tp1=0;
	for (int i=0; i<N; i++) par[i]=-1, im[i]=i, dep[i]=0;
	for (int i=N-1, t=0; i>=0; i--) {
		for (int j:V[i]) {
			if (j>i) Un1(i, j);
		}
		for (; t<Q&&sl[t].l>=i; t++) {
			int l=sl[t].s; while(par[l]!=-1) l=par[l];
			sl[t].nd=im[l];
		}
	}
	tr1.dfs(tr1.tp-1);
}

void Un2(int a, int b) {
	while (par[a]!=-1) a=par[a];
	while (par[b]!=-1) b=par[b];
	if (a==b) return ;
	if (dep[a]<dep[b]) swap(a, b);
	par[b]=a, dep[a]=max(dep[a], dep[b]+1);
	tr2.in(im[a], im[b]);
	im[a]=tr2.tp-1;
}

void f2() {
	tr2.tp=N, tr2.tp1=0;
	for (int i=0; i<N; i++) par[i]=-1, im[i]=i, dep[i]=0;
	for (int i=0, t=0; i<N; i++) {
		for (int j:V[i]) {
			if (j<i) Un2(i, j);
		}
		for (; t<Q&&er[t].l<=i; t++) {
			int l=er[t].s; while(par[l]!=-1) l=par[l];
			er[t].nd=im[l];
		}
	}
	tr2.dfs(tr2.tp-1);
}

pii ar[200010];
int seg[(1<<20)];

vim check_validity(int N_, vim X, vim Y, vim S, vim E, vim L, vim R) {
	N=N_; M=X.size(); Q=S.size();
	for (int i=0; i<M; i++) {
		V[X[i]].push_back(Y[i]);
		V[Y[i]].push_back(X[i]);
	}
	for (int i=0; i<Q; i++) {
		sl[i]={S[i], L[i], i, 0};
		er[i]={E[i], R[i], i, 0};
	}

	sort(sl, sl+Q, [](sler a, sler b){return a.l>b.l;});
	sort(er, er+Q, [](sler a, sler b){return a.l<b.l;});
	f1(); f2();
	sort(sl, sl+Q, [](sler a, sler b){return a.n<b.n;});
	sort(er, er+Q, [](sler a, sler b){return a.n<b.n;});

	for (int i=0; i<N; i++) {
		ar[i]={tr1.s[i], tr2.s[i]};
		assert(tr1.s[i]==tr1.e[i]&&tr2.s[i]==tr2.e[i]);
	}
	sort(ar, ar+N);

	for (int i=0; i<Q; i++) {
		int nd1=sl[i].nd, nd2=er[i].nd;
		Qu[i]={tr1.s[nd1], tr1.e[nd1], tr2.s[nd2], tr2.e[nd2], i, 0};
	}
	sort(Qu, Qu+Q, [](Query a, Query b){return a.x2<b.x2;});

	int mx=0;
	for (int i=0, j=0; i<Q; i++) {
		for (; j<N && ar[j].fi<=Qu[i].x2; j++) for (int k=(1<<19)+ar[j].se; k; k/=2) seg[k]=max(seg[k], ar[j].fi);
		mx=0;
		for (int k=(1<<19)+Qu[i].y1, l=(1<<19)+Qu[i].y2; k<=l; k/=2, l/=2) {
			if (k%2) mx=max(mx, seg[k++]);
			if (l%2==0) mx=max(mx, seg[l--]);
		}
		if (mx>=Qu[i].x1) Qu[i].ans=1;
		else Qu[i].ans=0;
	}
	sort(Qu, Qu+Q, [](Query a, Query b){return a.n<b.n;});

	vim ans;
	for (int i=0; i<Q; i++) ans.push_back(Qu[i].ans);
	return ans;
}

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