Submission #138675

#	Time	Username	Problem	Language	Result	Execution time	Memory
138675		ckodser	Werewolf (IOI18_werewolf)	C++14	100 / 100	979 ms	143604 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
#define ll int
#define pb push_back
#define ld long double
#define F first
#define S second
#define mp make_pair
#define pii pair<ll,ll> 

using namespace :: std;

const ll maxn=5e5+500;
const ll inf=1e9+900;

ll seg[maxn*4];
ll findMin(ll L,ll R,ll node,ll l,ll r){
    if(l<=L && R<=r){
	return seg[node];
    }
    if(r<=L || R<=l)return inf;
    ll mid=(L+R)/2;
    return min(findMin(L,mid,2*node,l,r),findMin(mid,R,2*node+1,l,r));
}
void update(ll L,ll R,ll node,ll x,ll v){
    if(L+1==R){
	seg[node]=v;
	return;
    }
    ll mid=(L+R)/2;
    if(x<mid){
	update(L,mid,2*node,x,v);
    }else{
	update(mid,R,2*node+1,x,v);
    }
    seg[node]=min(seg[2*node],seg[2*node+1]);
}

void bild(){
    fill(seg,seg+maxn*4,inf);
}



vector<ll> c[2];

ll n,q;
ll kojc1[maxn];
vector<ll> ves[maxn];
vector<ll>  findAns(vector<ll> l,vector<ll> r,vector<ll> L,vector<ll> R){
    for(ll i=0;i<n;i++){
	kojc1[c[1][i]]=i;
    }
    vector<ll> ans;
    ans.resize(q);
    for(ll i=0;i<q;i++){
	l[i]=max(l[i],0);
	r[i]=min(r[i],n);
	L[i]=max(L[i],0);
	R[i]=min(R[i],n);
	if(!(l[i]>=r[i] || L[i]>=R[i])){
	    ves[l[i]].pb(i);
	}
    }
    bild();
    for(ll i=n-1;i>=0;i--){
	update(0,n,1,kojc1[c[0][i]],i);
	for(auto y:ves[i]){
	    ll u=findMin(0,n,1,L[y],R[y]);
	    if(u<r[y]){
		ans[y]=1;
	    }
	}
    }
    return ans;
}




ll m;
vector<ll> ger[maxn];
ll par[maxn];
bool hast[maxn];


vector<ll> tree[2][maxn];
ll st[2][maxn];
ll et[2][maxn];
ll tt=0;


ll cnt=-1;

ll findPar(ll x){
    if(par[x]==x)return x;
    par[x]=findPar(par[x]);
    return par[x];
}
void clearr(){
    cnt++;
    for(ll i=0;i<maxn;i++){
	par[i]=i;
	hast[i]=0;
    }
}
void add(ll x){
    hast[x]=1;
    for(auto v:ger[x]){
	if(hast[v]){
	    ll r=findPar(v);
	    if(r!=x){
		par[r]=x;
		tree[cnt][x].pb(r);
	    }
	}
    }
}
void dfs(ll a,ll b){
    c[b].pb(a);
    st[b][a]=tt++;
    for(auto v:tree[b][a]){
	dfs(v,b);
    }
    et[b][a]=tt;
}

vector<ll> li[maxn];
vector<ll> ri[maxn];



ll lp[maxn];
ll rp[maxn];
vector<int> check_validity(int N,vector<int> X,vector<int> Y,vector<int> S,vector<int> E,vector<int> L,vector<int> R) {
    q = S.size();
    m=X.size();
    n=N;
    for(ll i=0;i<m;i++){
        ger[X[i]].pb(Y[i]);
        ger[Y[i]].pb(X[i]);
    }
    for(ll i=0;i<q;i++){
	li[L[i]].pb(i);
	ri[R[i]].pb(i);
    }
    clearr();
    for(ll i=0;i<n;i++){
	add(i);
	for(auto x:ri[i]){
	    rp[x]=findPar(E[x]);
	}
    }
    ll rotr=findPar(0);
    clearr();
    for(ll i=n-1;i>=0;i--){
	add(i);
	for(auto x:li[i]){
	    lp[x]=findPar(S[x]);
	}
    }
    ll rotl=findPar(0);
    tt=0;
    dfs(rotr,0);
    tt=0;
    dfs(rotl,1);
    
    vector<ll> A,B,a,b;
    A.resize(q);B.resize(q);a.resize(q);b.resize(q);
    for(ll i=0;i<q;i++){
	ll X=rp[i];
	ll Y=lp[i];
	a[i]=st[0][X];
	b[i]=et[0][X];
	A[i]=st[1][Y];
	B[i]=et[1][Y];
    }

    vector<int> ans=findAns(a,b,A,B);

    for(ll i=0;i<q;i++){
	if(S[i]<L[i] || E[i]>R[i])ans[i]=0;
    }
    return ans;
}

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