Submission #286164

#	Time	Username	Problem	Language	Result	Execution time	Memory
286164		dvdg6566	Werewolf (IOI18_werewolf)	C++14	100 / 100	1157 ms	118360 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
typedef long double ld;
#define pb emplace_back
#define mp make_pair
#define f first
#define s second
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define lb lower_bound
#define ub upper_bound
const int MAXN=200001;
const ll MOD=1e9+7;
const ll INF = 1e9;
const int MAXL = 18;

vpi edges;
vector<vi> V[2];
vi pre[2];
vi ipre[2];
vi post[2];
vi ord;
int p[MAXN][MAXL][2];

int up[MAXN];
int par(int x){return(up[x]==x)?x:up[x] = par(up[x]);}
int gx;
int N;

void dfs(int x,int pa,int a){
	pre[a][x]=gx;
	ipre[a][gx]=x;
	++gx;
	p[x][0][a] = pa;
	for(int i=1;i<MAXL;++i){
		if(p[x][i-1][a] == -1)continue;
		int b=p[x][i-1][a];
		p[x][i][a] = p[b][i-1][a];
	}

	for(auto t:V[a][x])if(t!=pa)dfs(t,x,a);
	post[a][x]=gx-1;
}

void generate_tree(int a){
	for(int i=0;i<N;++i){
		up[i]=i;
	}
	pre[a].resize(N,0);
	ipre[a].resize(N,0);
	post[a].resize(N,0);

	V[a].resize(N);
	gx=0;
	for(auto i:edges){
		if(par(i.f) == par(i.s))continue;
		i.s=par(i.s);
		assert(up[i.f] == i.f);
		if(a==0)assert(i.f>i.s);
		else assert(i.f<i.s);
		V[a][i.f].pb(i.s);
		up[i.s]=par(i.f);
	}
	if(a==0)dfs(N-1,-1,a);
	else dfs(0,-1,a);
}

bool B[MAXN];

typedef pair<pi,pi> pp;
vector<pp> sweep[MAXN]; // V[preA] = {index, postA, preB, postB}

struct node{
	int s,e,m,v;
	node *l,*r;
	node(int _s,int _e):s(_s),e(_e){
		m=(s+e)/2;
		v=1e9;
		if(s!=e){
			l=new node(s,m);r=new node(m+1,e);
		}
	}
	void up(int x,int va){
		if(s==e){v=va;return;}
		if(x<=m)l->up(x,va);
		else r->up(x,va);
		v=min(l->v,r->v);
	}
	int rmin(int x,int y){
		if(s==x&&e==y)return v;
		if(y<=m)return l->rmin(x,y);
		else if (x>m)return r->rmin(x,y);
		return min(l->rmin(x,m),r->rmin(m+1,y));
	}
}*root;

std::vector<int> check_validity(int _N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
  	N=_N;
  	memset(p,-1,sizeof(p));
  	for(int i=0;i<SZ(X);++i){
  		if(Y[i] > X[i])swap(X[i],Y[i]);
  		edges.pb(X[i],Y[i]);
  	}
  	sort(ALL(edges));
  	for(int i=0;i<N;++i)ord.pb(i);
  	generate_tree(0);


  	for(auto &i:edges)swap(i.f,i.s);
  	sort(ALL(edges));reverse(ALL(edges));
  	generate_tree(1);
  	// for(int i=0;i<N;++i)cout<<pre[1][i]<<' '<<post[1][i]<<'\n';

  	int Q = S.size();
  	std::vector<int> A(Q);
  	for (int i = 0; i < Q; ++i) {
    	A[i] = 0;
  	}

  	for(int t=0;t<SZ(S);++t){
  		int st=S[t];

  		for(int i=MAXL-1;i>=0;--i){
  			if(p[st][i][1] >= L[t]){
  				st=p[st][i][1];
  			}
  		}

  		int en=E[t];
  		for(int i=MAXL-1;i>=0;--i){
  			if(p[en][i][0] != -1 && p[en][i][0] <= R[t]){
  				en=p[en][i][0];
  			}
  		}
  		sweep[pre[1][st]].pb(mp(post[1][st], t), mp(pre[0][en], post[0][en]));
  	}
  	// In the seg tree pairs are (preB, preA)
  	root=new node(0,N-1);
  	for(int i=N-1;i>=0;--i){
  		int node = ipre[1][i];
  		root->up(pre[0][node], pre[1][node]);
  		for(auto x:sweep[i]){
  			int ind=x.f.s;
  			int m=root->rmin(x.s.f,x.s.s);
  			if(x.f.f >= m)A[ind]=1;
  			// cerr<<"Query "<<ind<<' '<<x.f.f<<' '<<m<<'\n';
  		}
  	}
  	
  	return A;
}

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