Submission #286158

#	Time	Username	Problem	Language	Result	Execution time	Memory
286158		dvdg6566	Werewolf (IOI18_werewolf)	C++14	15 / 100	4070 ms	64360 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];

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 st2=S[t];
  		// while(st!=0 && p[1][st] >= L[t]){
  		// 	st=p[1][st];
  		// }
  		// cerr<<"As human can go to "<<st<<'\n';

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

  		for(int i=0;i<N;++i){
  			if(pre[0][i] < pre[0][en] || pre[0][i] > post[0][en])continue;
  			if(pre[1][i] < pre[1][st] || pre[1][i] > post[1][st])continue;

  			assert(i>=L[t]&&i<=R[t]);
  			// cerr<<"Middle ground "<<i<<' '<<t<<'\n';
  			A[t]=1;
  		}
  		// cerr<<"As wolf can go to "<<en<<'\n';
  		

  	}


  	
  	return A;
}

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