Submission #138666

#	Time	Username	Problem	Language	Result	Execution time	Memory
138666		ckodser	Werewolf (IOI18_werewolf)	C++14	15 / 100	4037 ms	127208 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];

void bild(ll l,ll r,ll node){
    fill(seg,seg+maxn,inf);
}
ll findMin(ll L,ll R,ll node,ll l,ll r){
    ll ans=inf;
    for(ll i=l;i<r;i++)ans=min(ans,seg[i]);
    return ans;
}
ll update(ll L,ll R,ll node,ll x,ll v){
    seg[x]=v;
}

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(0,n,1);
    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;
}

Compilation message (stderr)

werewolf.cpp: In function 'int update(int, int, int, int, int)':
werewolf.cpp:28:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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