Submission #138657

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

vector<ll> c[2];

bool is_barkh(ll l,ll r,ll L,ll R){
    set<ll> st;
    for(ll i=l;i<r;i++){
	st.insert(c[0][i]);
    }
    for(ll i=L;i<R;i++){
	ll v=c[1][i];
	if(st.find(v)!=st.end())return 1;
    }
    return 0;
}

ll n,m,q;
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<int> ans(q);
    for(ll i=0;i<q;i++){
	ll X=rp[i];
	ll Y=lp[i];
	ans[i]=is_barkh(st[0][X],et[0][X],st[1][Y],et[1][Y]);
    }
    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: 0 / 34
• Subtask 4: 0 / 51