Submission #532208

#	Time	Username	Problem	Language	Result	Execution time	Memory
532208		nicholask	Werewolf (IOI18_werewolf)	C++14	100 / 100	1409 ms	188892 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
using namespace std;
using pii=pair <int,int>;
int dsu[400040];
void init(int sz){
    for (int i=0; i<sz; i++) dsu[i]=i;
}
int prt(int node){
    if (dsu[node]==node) return node;
    return dsu[node]=prt(dsu[node]);
}
void unn(int u,int v){
    u=prt(u); v=prt(v);
    if (u==v) return;
    dsu[u]=dsu[v];
}
bool cmp1(pii a,pii b){
    return min(a.x,a.y)>min(b.x,b.y);
}
bool cmp2(pii a,pii b){
    return max(a.x,a.y)<max(b.x,b.y);
}
vector <int> humanGraph[400040],wolfGraph[400040];
int humanP[400040],wolfP[400040]; //leaves permutation
pii humanR[400040],wolfR[400040]; //range
int tme;
int humanval[400040],wolfval[400040];
int humanlca[400040][19],wolflca[400040][19];
pii humanDfs(int cur,int prv){
    humanlca[cur][0]=prv;
    if (humanGraph[cur].empty()){
        humanP[tme]=cur;
        tme++;
        return humanR[cur]={tme-1,tme-1};
    }
    vector <pii> ranges;
    for (auto i:humanGraph[cur]) ranges.pb(humanDfs(i,cur));
    sort(ranges.begin(),ranges.end());
    return humanR[cur]={ranges.front().x,ranges.back().y};
}
pii wolfDfs(int cur,int prv){
    wolflca[cur][0]=prv;
    if (wolfGraph[cur].empty()){
        wolfP[tme]=cur;
        tme++;
        return wolfR[cur]={tme-1,tme-1};
    }
    vector <pii> ranges;
    for (auto i:wolfGraph[cur]) ranges.pb(wolfDfs(i,cur));
    sort(ranges.begin(),ranges.end());
    return wolfR[cur]={ranges.front().x,ranges.back().y};
}
struct wavelet{
	int lo,hi;
	wavelet *lhs=0,*rhs=0;
	vector <int> b;
	wavelet(vector<int>v):wavelet(v.begin(),v.end(),*min_element(v.begin(),v.end()),*max_element(v.begin(),v.end())){};
	~wavelet(){
		if (lhs) delete lhs;
		if (rhs) delete rhs;
	}
	template <typename T> wavelet(T from,T to,int lo_,int hi_){
		lo=lo_;
		hi=hi_;
		if (from>=to||lo==hi) return;
		int mi=lo+(hi-lo)/2;
		auto f=[&](int r){
			return r<=mi;
		};
		b.reserve(to-from+1);
		b.push_back(0);
		for (auto it=from; it!=to; it++) b.push_back(b.back()+f(*it));
		auto mit=stable_partition(from,to,f);
		lhs=new wavelet(from,mit,lo,mi);
		rhs=new wavelet(mit,to,mi+1,hi);
	}
	int lte(int l,int r,int k){
		if (l>r||k<lo) return 0;
		if (hi<=k) return r-l+1;
		return this->lhs->lte(b[l],b[r+1]-1,k)+this->rhs->lte(l-b[l],r-b[r+1],k);
	}
};
vector <int> check_validity(int N,vector <int> X,vector <int> Y,vector <int> S,vector <int> E,vector <int> L,vector <int> R){
    int m=X.size();
    vector <pii> edge;
    for (int i=0; i<m; i++) edge.pb({X[i],Y[i]});
    sort(edge.begin(),edge.end(),cmp1);
    init(2*N);
    int cur=N;
    for (int i=0; i<N; i++) humanval[i]=i;
    for (auto i:edge){
        if (prt(i.x)==prt(i.y)) continue;
        humanGraph[cur].pb(prt(i.x));
        humanGraph[cur].pb(prt(i.y));
        humanval[cur]=min(humanval[prt(i.x)],humanval[prt(i.y)]);
        unn(i.x,cur);
        unn(i.y,cur);
        cur++;
    }
    tme=0;
    for (int i=0; i<2*N; i++){
        for (int j=0; j<19; j++) humanlca[i][j]=-1;
    }
    humanDfs(cur-1,-1);
    for (int j=1; j<19; j++){
        for (int i=0; i<2*N; i++){
            if (humanlca[i][j-1]==-1) humanlca[i][j]=-1;
            else humanlca[i][j]=humanlca[humanlca[i][j-1]][j-1];
        }
    }
    sort(edge.begin(),edge.end(),cmp2);
    init(2*N);
    cur=N;
    for (int i=0; i<N; i++) wolfval[i]=i;
    for (int i=N; i<2*N; i++) wolfval[i]=1e9; 
    for (auto i:edge){
        if (prt(i.x)==prt(i.y)) continue;
        wolfGraph[cur].pb(prt(i.x));
        wolfGraph[cur].pb(prt(i.y));
        wolfval[cur]=max(wolfval[prt(i.x)],wolfval[prt(i.y)]);
        unn(i.x,cur);
        unn(i.y,cur);
        cur++;
    }
    tme=0;
    for (int i=0; i<2*N; i++){
        for (int j=0; j<19; j++) wolflca[i][j]=-1;
    }
    wolfDfs(cur-1,-1);
    for (int j=1; j<19; j++){
        for (int i=0; i<2*N; i++){
            if (wolflca[i][j-1]==-1) wolflca[i][j]=-1;
            else wolflca[i][j]=wolflca[wolflca[i][j-1]][j-1];
        }
    }
    vector <int> poshuman(N);
    for (int i=0; i<N; i++) poshuman[humanP[i]]=i;
    vector <int> r(N);
    for (int i=0; i<N; i++) r[i]=poshuman[wolfP[i]];
    wavelet tree(r);
    vector <int> ans;
    for (int Q=0; Q<S.size(); Q++){
        int st=S[Q],en=E[Q];
        if (humanval[st]<L[Q]||wolfval[en]>R[Q]){
            ans.pb(-1);
            continue;
        }
        for (int i=18; i>=0; i--){
            if (humanlca[st][i]==-1) continue;
            if (humanval[humanlca[st][i]]>=L[Q]) st=humanlca[st][i];
        }
        for (int i=18; i>=0; i--){
            if (wolflca[en][i]==-1) continue;
            if (wolfval[wolflca[en][i]]<=R[Q]) en=wolflca[en][i];
        }
        if (tree.lte(wolfR[en].x,wolfR[en].y,humanR[st].y)!=tree.lte(wolfR[en].x,wolfR[en].y,humanR[st].x-1)) ans.pb(1);
        else ans.pb(0);
    }
    return ans;
}
/*
signed main(){
    int N,M,Q;
    cin>>N>>M>>Q;
    vector <int> X,Y,S,E,L,R;
    for (int i=0; i<M; i++){
        int xj,yj;
        cin>>xj>>yj;
        X.pb(xj);
        Y.pb(yj);
    }
    for (int i=0; i<Q; i++){
        int si,ei,li,ri;
        cin>>si>>ei>>li>>ri;
        S.push_back(si);
        E.push_back(ei);
        L.push_back(li);
        R.push_back(ri);
    }
    vector <int> ans=check_validity(N,X,Y,S,E,L,R);
    for (int i:ans) cout<<i<<' ';
}
*/

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:146:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |     for (int Q=0; Q<S.size(); Q++){
      |                   ~^~~~~~~~~

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