Submission #119672

#	Time	Username	Problem	Language	Result	Execution time	Memory
119672		imyujin	Werewolf (IOI18_werewolf)	C++14	100 / 100	1596 ms	142468 KiB

werewolf

#include "werewolf.h"
#include<vector>
#include<algorithm>

using namespace std;

#define MAXN 200005
#define fi first
#define se second

typedef pair<int, int> pi;

struct tree{
	int c[2*MAXN], par[20][2*MAXN], ro[2*MAXN], mn[2*MAXN], mx[2*MAXN];
	vector<int> chi[2*MAXN];
	int s[MAXN], sn;
	int tn;
}tr[2];

int N, M;
vector<pi> e;
int seg[MAXN*4], G[MAXN][2];

bool cmp(pi a, pi b){
	return max(a.fi, a.se)<max(b.fi, b.se);
}

int getro(tree* T, int x){
	if(T->ro[x]==x) return x;
	return T->ro[x]=getro(T, T->ro[x]);
}

void dfs(tree* T, int x){
	if(x<N){
		T->mn[x]=T->mx[x]=T->sn;
		T->s[T->sn++]=x;
	}
	else{
		T->mn[x]=N;
		T->mx[x]=0;
		for(auto a:T->chi[x]){
			dfs(T, a);
			T->mn[x]=min(T->mn[x], T->mn[a]);
			T->mx[x]=max(T->mx[x], T->mx[a]);
		}
	}
}

void mktr(tree* T){
	for(int i=0; i<N; i++) T->c[i]=T->ro[i]=T->mn[i]=T->mx[i]=i;
	sort(e.begin(), e.end(), cmp);
	T->tn=N;
	for(auto a:e){
		int r1=getro(T, a.fi), r2=getro(T, a.se);
		if(r1!=r2){
			T->par[0][r1]=T->par[0][r2]=T->par[0][T->tn]=T->ro[r1]=T->ro[r2]=T->ro[T->tn]=T->tn;
			T->chi[T->tn].push_back(r1);
			T->chi[T->tn].push_back(r2);
			T->c[T->tn]=max(a.fi, a.se);
			T->tn++;
		}
	}
	for(int i=1; i<20; i++) for(int j=0; j<T->tn; j++) T->par[i][j]=T->par[i-1][T->par[i-1][j]];
	T->sn=0;
	dfs(T, T->tn-1);
}

int goup(tree* T, int x, int l){
	for(int i=19; i>=0; i--) if(T->c[T->par[i][x]]<=l) x=T->par[i][x];
	return x;
}

void updseg(int idx, int l, int r, int x){
	seg[idx]++;
	if(l<r){
		int m=l+r>>1;
		if(x<=m) updseg(idx*2, l, m, x);
		else updseg(idx*2+1, m+1, r, x);
	}
}

int gseg(int idx, int l, int r, int x, int y){
	if(x<=l&&r<=y) return seg[idx];
	if(r<x||y<l) return 0;
	int m=l+r>>1;
	return gseg(idx*2, l, m, x, y)+gseg(idx*2+1, m+1, r, x, y);
}

vector<int> check_validity(int n, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
	int Q=S.size();
	vector<int> ans(Q);
	vector<int> B[MAXN];

	N=n;
	M=X.size();

	for(int i=0; i<M; i++) e.push_back(make_pair(N-X[i]-1, N-Y[i]-1));
	mktr(&tr[0]);
	for(int i=0; i<M; i++) e[i]=make_pair(X[i], Y[i]);
	mktr(&tr[1]);

	for(int i=0; i<Q; i++) G[i][0]=goup(&tr[0], N-S[i]-1, N-L[i]-1);
	for(int i=0; i<Q; i++) G[i][1]=goup(&tr[1], E[i], R[i]);

	for(int i=0; i<Q; i++){
		if(tr[0].mn[G[i][0]]>0) B[tr[0].mn[G[i][0]]-1].push_back(i);
		B[tr[0].mx[G[i][0]]].push_back(i);
	}

	for(int i=0; i<N; i++){
		updseg(1, 0, N-1, tr[1].mx[N-tr[0].s[i]-1]);
		for(auto a:B[i])
			ans[a]+=(tr[0].mx[G[a][0]]==i?1:-1)*gseg(1, 0, N-1, tr[1].mn[G[a][1]], tr[1].mx[G[a][1]]);
	}
	for(int i=0; i<Q; i++) ans[i]=min(ans[i], 1);

	return ans;
}

Compilation message (stderr)

werewolf.cpp: In function 'void updseg(int, int, int, int)':
werewolf.cpp:76:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m=l+r>>1;
         ~^~
werewolf.cpp: In function 'int gseg(int, int, int, int, int)':
werewolf.cpp:85:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~

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