Submission #286148

#	Time	Username	Problem	Language	Result	Execution time	Memory
286148		dvdg6566	Werewolf (IOI18_werewolf)	C++14	0 / 100	425 ms	76648 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;

vpi edges;
vector<vi> V[2];
vi pre[2];
vi ipre[2];
vi post[2];
vi ord;
vi p[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[a][x] = pa;
	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);
	p[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);
		V[a][i.f].pb(i.s);
		up[i.s]=par(i.f);
	}
	if(a==0)dfs(N-1,-1,a);
	else dfs(1,-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;
  	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);

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

  		int en=E[t];
  		while(en!=N-1 && p[0][en] <= R[t]){
  			en=p[0][en];
  		}

  		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: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51