Submission #261238

#	Time	Username	Problem	Language	Result	Execution time	Memory
261238		medk	Werewolf (IOI18_werewolf)	C++14	100 / 100	1206 ms	81648 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"

#define ll long long
#define pb push_back
#define x first
#define y second
#define sz(u) (int)(u.size())
#define all(u) u.begin(),u.end()

using namespace std;

int n,m,q,timer,root[2];
vector<vector<int>> g;
vector<vector<pair<int,int>>> tr[2];
vector<int> dsu,sz, in[2], out[2];
vector<pair<int,int>> par[2],trav[2];
vector<int> bit;

void upd(int x, int v){
	for(;x<=n;x+=x&-x) bit[x]+=v;
}

int sum(int x){
	int ret=0;
	for(;x>0;x-=x&-x) ret+=bit[x];
	return ret;
}

int getp(int x){
	return dsu[x]==x?x:dsu[x]=getp(dsu[x]);
}

void connect(int u, int v, int t){
	u=getp(u), v=getp(v);
	if(u==v) return;
	if(sz[u]<sz[v]) swap(u,v);
	dsu[v]=u;
	sz[u]+=sz[v];
	par[t][v]={timer,u};
	tr[t][u].pb({timer,v});
}

bool connected(int u, int v){
	return getp(u)==getp(v);
}

void dfs(int u, int t){
	in[t][u]=sz(trav[t]);
	trav[t].pb({u,in[t][u]});
	for(auto v:tr[t][u]){
		dfs(v.y,t);
	}
	out[t][u]=sz(trav[t])-1;
}

pair<int,int> getblock(int u, int L, int t){
	while(par[t][u].x<=L) u = par[t][u].y;
	int l=-1, r=sz(tr[t][u])-1;
	while(l<r){
		int md=(l+r+1)/2;
		if(tr[t][u][md].x>L) r=md-1;
		else l=md;
	}
	if(l==-1) return {in[t][u],in[t][u]};
	return {in[t][u],out[t][tr[t][u][l].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){
	n=N;
	m=sz(X);
	q=sz(S);
	g.resize(n), dsu.resize(n), sz.resize(n), tr[0].resize(n), tr[1].resize(n), par[0].resize(n), par[1].resize(n);
	in[0].resize(n), in[1].resize(n), out[0].resize(n), out[1].resize(n), bit.resize(n+1);
	for(int i=0;i<n;i++) dsu[i]=i, sz[i]=1, par[0][i]=par[1][i]={(int)1e9,-1};
	for(int i=0;i<m;i++){
		g[X[i]].pb(Y[i]);	
		g[Y[i]].pb(X[i]);	
	}
	for(int i=0;i<n;i++) sort(all(g[i]));
	for(int i=0;i<n;i++){
		timer=i;
		for(int u:g[i]){
			if(i<u) continue;
			connect(i,u,0);
		}
	}
	root[0]=getp(0);
	dfs(root[0],0);
	for(int i=0;i<n;i++) dsu[i]=i, sz[i]=1;
	for(int i=n-1;i>=0;i--){
		timer=n-1-i;
		for(int u:g[i]){
			if(i<u) connect(i,u,1);
		}
	}
	root[1]=getp(0);
	dfs(root[1],1);
	sort(all(trav[0]));
	sort(all(trav[1]));
	for(int i=0;i<n;i++) trav[1][i].x=trav[0][i].y, swap(trav[1][i].x,trav[1][i].y);
	sort(all(trav[1]));
	vector<pair<pair<int,int>,int>> queriesL[n], queriesR[n];
	vector<int> cnt(q);
	for(int i=0;i<q;i++){
		pair<int,int> p1=getblock(E[i],R[i],0);
		pair<int,int> p2=getblock(S[i],n-1-L[i],1);
		if(p2.x>0 && p1.x>0) queriesL[p2.x-1].pb({{p1.x-1,i},-1});
		if(p1.x>0) queriesL[p2.y].pb({{p1.x-1,i},1});
		if(p2.x>0 && p1.y<n-1) queriesR[p2.x-1].pb({{p1.y+1,i},-1});
		if(p1.y<n-1) queriesR[p2.y].pb({{p1.y+1,i},1});
		cnt[i]=p2.y-p2.x+1;
	}
	for(int i=0;i<n;i++){
		upd(trav[1][i].y+1,1);
		for(auto p:queriesL[i]){
			cnt[p.x.y]-=sum(p.x.x+1)*p.y; 
		}
	}
	for(int i=0;i<=n;i++) bit[i]=0;
	for(int i=0;i<n;i++){
		upd(trav[1][i].y+1,1);
		for(auto p:queriesR[i]){
			cnt[p.x.y]-=(sum(n)-sum(p.x.x))*p.y; 
		}
	}
	vector<int> ret(q);
	for(int i=0;i<q;i++) ret[i]=(bool)(cnt[i]>0);
	return ret;
}

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