제출 #520295

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
520295		new_acc	늑대인간 (IOI18_werewolf)	C++14	100 / 100	1301 ms	257668 KiB

werewolf

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int N=6e5+10;
const int L=20;
const int SS=1<<20;
vector<int>graf[N];
int seg[SS*2+10],jump[N][L+1];
int val[N][L+1];
vector<pair<int,int> >tr[N];
pair<int,int>pp[N];
int fau[N],num[N];
vector<pair<int,int> >tr2[N];
int jump2[N][L+1];
int val2[N][L+1];
int li;
int pre[N];
int m;
int naj[N],naj2[N];
vector<int>zap[N];
void add(int a,int ind){
	seg[ind+=SS]=a;
	for(ind>>=1;ind>0;ind>>=1) seg[ind]=max(seg[ind*2],seg[ind*2+1]);
}
int Query(int a,int b){
	int res=0;
	for(a+=SS-1,b+=SS+1;(a>>1)!=(b>>1);a>>=1,b>>=1){
		if(!(a&1)) res=max(res,seg[a+1]);
		if(b&1) res=max(res,seg[b-1]);
	}
	return res;
}
void dfs(int v,int o,int x=INT_MAX){
	jump[v][0]=o;
	val[v][0]=x;
	for(int i=1;i<=L;i++) jump[v][i]=jump[jump[v][i-1]][i-1],val[v][i]=min(val[v][i-1],val[jump[v][i-1]][i-1]);
	li++;
	pp[v].fi=li;
	for(auto u:tr[v]){
		if(u.fi==o) continue;
		dfs(u.fi,v,u.se);
	}
	pp[v].se=li;
}
int zn(int a,int c){
	int res=a;
	for(int i=L;i>=0;i--)
		if(val[a][i]>=c) res=jump[a][i],a=jump[a][i];
	return res;
}
int Find(int a){
	if(fau[a]==a) return a;
	return fau[a]=Find(fau[a]);
}
void Union(int a,int b,int c,int xd){
	a=Find(a),b=Find(b);
	if(a==b) return;
	tr[xd].push_back({num[b],c}),tr[xd].push_back({num[a],c});
	fau[a]=b;
	num[b]=xd;
}
void Union2(int a,int b,int c,int xd){
	a=Find(a),b=Find(b);
	if(a==b) return;
	tr2[xd].push_back({num[b],c}),tr2[xd].push_back({num[a],c});
	fau[a]=b;
	num[b]=xd;
}
void dfs2(int v,int o,int x=0){
	jump2[v][0]=o,val2[v][0]=x;
	if(v<=m) pre[++li]=v;
	else ++li;
	for(int i=1;i<=L;i++) jump2[v][i]=jump2[jump2[v][i-1]][i-1],val2[v][i]=max(val2[v][i-1],val2[jump2[v][i-1]][i-1]);
	naj2[v]=INT_MAX;
	int xd=li;
	for(auto u:tr2[v]){
		if(u.fi==o) continue;
		dfs2(u.fi,v,u.se);
		naj2[v]=min(naj2[v],naj2[u.fi]);
		naj[v]=max(naj[v],naj[u.fi]);
	}
	if(naj[v]==0) naj2[v]=xd,naj[v]=xd;
}
int zn2(int a,int c){
	int res=a;
	for(int i=L;i>=0;i--)
		if(val2[a][i]<=c) res=jump2[a][i],a=jump2[a][i];
	return res;
}
vector<int> check_validity(int n,vector<int> x,vector<int> y,vector<int> s,vector<int> e,vector<int> l, vector<int> r){
	m=n;
	vector<int>res(s.size());
	for(int i=0;i<(int)s.size();i++) s[i]++,e[i]++,l[i]++,r[i]++;
	for(int i=0;i<(int)x.size();i++) x[i]++,y[i]++,graf[x[i]].push_back(y[i]),graf[y[i]].push_back(x[i]);
	int wsk=n;
	for(int i=1;i<=n;i++) fau[i]=i,num[i]=i;
	for(int i=n;i>=1;i--){
		for(auto u:graf[i])
			if(u>i&&Find(i)!=Find(u)) Union(i,u,i,++wsk);
	}
	for(int i=1;i<=n;i++) fau[i]=i,num[i]=i;
	dfs(wsk,wsk);
	wsk=n,li=0;
	for(int i=1;i<=n;i++){
		for(auto u:graf[i])
			if(u<i&&Find(i)!=Find(u)) Union2(i,u,i,++wsk);
	}
	dfs2(wsk,wsk);
	for(int i=0;i<(int)s.size();i++){
		int xd=zn2(e[i],r[i]);
		zap[naj[xd]].push_back(i);
	}
	for(int i=1;i<=wsk;i++){
		if(pre[i]==0) continue;
		add(i,pp[pre[i]].fi);
		for(auto u:zap[i]){
			int lew=naj2[zn2(e[u],r[u])];
			int w=zn(s[u],l[u]);
			int xd=Query(pp[w].fi,pp[w].se);
			if(xd>=lew) res[u]=1;
			else res[u]=0;
		}
	}

	return res;
}
/*int main(){
	//vector<int> v=check_validity(4,{1,2,3,4,3,5},{1,2,3,4,0,2},{4,4,5},{2,2,4},{1,2,3},{2,2,4});
	//for(auto u:v) cout<<u<<"\n";
}	*/

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