Submission #138616

#	Time	Username	Problem	Language	Result	Execution time	Memory
138616		ckodser	Werewolf (IOI18_werewolf)	C++14	15 / 100	609 ms	73024 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 kmaxn=3100;
const ll inf=1e9+900;
const ll logg=20;

ll n,m,q;
vector<ll> ger[maxn];
vector<ll> b;
ll koj[maxn];
ll mn[maxn][logg];
ll mx[maxn][logg];
ll tt[maxn];

ll findMax(ll l,ll r){
    if(l>r)swap(l,r);
    ll t=tt[r-l+1];
    ll res=r-(1<<t)+1;
    return max(mx[l][t],mx[res][t]);
}
ll findMin(ll l,ll r){
    if(l>r)swap(l,r);
    ll t=tt[r-l+1];
    ll res=r-(1<<t)+1;
    return min(mn[l][t],mn[res][t]);
}
ll findAnsKhat(ll s,ll e,ll l,ll r){
    if(s<l || e>r)return 0;
    s=koj[s];
    e=koj[e];
    if(findMin(s,e)>=l || findMax(s,e)<=r)return 1;
    ll bb=s;
    ll ee=e;
    while(ee-bb>1){
	ll mid=(ee+bb)/2;
	if(findMin(s,mid)>=l){
	    bb=mid;
	}else{
	    ee=mid;
	}
    }
    return(findMax(bb,e)<=r);
}

void dfs(ll a,ll p=-1){
    koj[a]=b.size();
    b.pb(a);
    for(auto r:ger[a]){
	if(r!=p){
	    dfs(r,a);
	}
    }
}
bool vis[2][kmaxn];
bool findAns(ll s,ll e,ll l,ll r){
    if(s<l || e>r)return 0;
    memset(vis,0,sizeof vis);
    queue<ll> qu;
    qu.push(s);
    vis[0][s]=1;
    while(qu.size()){
	ll v=qu.front();
	qu.pop();
	for(auto u:ger[v]){
	    if(u>=l && !vis[0][u]){
		qu.push(u);
		vis[0][u]=1;
	    }
	}
    }
    qu.push(e);
    vis[1][e]=1;
    while(qu.size()){
	ll v=qu.front();
	qu.pop();
	for(auto u:ger[v]){
	    if(u<=r && !vis[1][u]){
		qu.push(u);
		vis[1][u]=1;
	    }
	}
    }
    for(ll i=0;i<n;i++){
	if(vis[0][i] && vis[1][i])return 1;
    }
    return 0;
}

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;
    vector<int> ans(q);
    for(ll i=0;i<m;i++){
        ger[X[i]].pb(Y[i]);
        ger[Y[i]].pb(X[i]);
    }
    if(q<=3000 && m<=6000 && n<=3000){
	for(ll i=0;i<q;i++){
	    ans[i]=findAns(S[i],E[i],L[i],R[i]);
	}
	return ans;
    }
    if(m!=n-1)return ans;
    ll star;
    for(ll i=0;i<n;i++){
	if(ger[i].size()>2)return ans;
	if(ger[i].size()==1){
	    star=i;
	}
    }		
    dfs(star);
    for(ll i=0;i<n;i++){
	mn[i][0]=b[i];
	mx[i][0]=b[i];
    }
    for(ll j=1;j<logg;j++){
	for(ll i=0;i<n;i++){
	    ll res=i+(1<<(j-1));
	    if(res<n){
		mn[i][j]=min(mn[i][j-1],mn[res][j-1]);
		mx[i][j]=max(mx[i][j-1],mx[res][j-1]);
	    }else{
		mn[i][j]=mn[i][j-1];
		mx[i][j]=mx[i][j-1];
	    }
	}
    }
    tt[1]=0;
    for(ll i=2;i<maxn;i++){
	tt[i]=1+tt[i/2];
    }
    for(ll i=0;i<q;i++){
	ans[i]=findAnsKhat(S[i],E[i],L[i],R[i]);
    }
    return ans;
}

Compilation message (stderr)

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:123:8: warning: 'star' may be used uninitialized in this function [-Wmaybe-uninitialized]
     dfs(star);
     ~~~^~~~~~

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