Submission #628239

#	Time	Username	Problem	Language	Result	Execution time	Memory
628239		alexander707070	Werewolf (IOI18_werewolf)	C++14	15 / 100	4070 ms	36340 KiB

werewolf

#include <bits/stdc++.h>
#define MAXN 200007
using namespace std;

const int bucket_sz=400;
int n,m,a,b,bucket[MAXN],q,l,r;

struct event{
    int id;
    int val;
    int tim;
};

struct qr{
    int s,e;
    int l,r;
    int id;

    inline friend bool operator < (qr fr,qr sc){
        if(bucket[fr.l]!=bucket[sc.l])return bucket[fr.l]<bucket[sc.l];
        else return fr.r<sc.r;
    }
};

vector<int> v[MAXN];
stack<event> sl,sr;
qr qs[MAXN];

int ldsu[MAXN],rdsu[MAXN],lsz[MAXN],rsz[MAXN];
int timl,timr;
vector<int> ans;

int rootL(int x){
    if(ldsu[x]==x)return ldsu[x];
    return rootL(ldsu[x]);
}

int rootR(int x){
    if(rdsu[x]==x)return rdsu[x];
    return rootR(rdsu[x]);
}

void connectL(int x,int y){
    timl++;
    int rootx=rootL(x);
    int rooty=rootL(y);
    if(rootx==rooty)return;

    if(lsz[rootx]<lsz[rooty])swap(rootx,rooty);
    sl.push({rooty,ldsu[rooty],timl});
    sl.push({-rootx,lsz[rootx],timl});
    ldsu[rooty]=rootx; lsz[rootx]+=lsz[rooty];
}

void connectR(int x,int y){
    timr++;
    int rootx=rootR(x);
    int rooty=rootR(y);
    if(rootx==rooty)return;

    if(rsz[rootx]<rsz[rooty])swap(rootx,rooty);
    sr.push({rooty,rdsu[rooty],timr});
    sr.push({-rootx,rsz[rootx],timr});
    rdsu[rooty]=rootx; rsz[rootx]+=rsz[rooty];
}

void undoL(){
    while(!sl.empty() and sl.top().tim==timl){
        if(sl.top().id<0)lsz[-sl.top().id]=sl.top().val;
        else ldsu[sl.top().id]=sl.top().val;
        sl.pop();
    }
    timl--;
}

void undoR(){
    while(!sr.empty() and sr.top().tim==timr){
        if(sr.top().id<0)rsz[-sr.top().id]=sr.top().val;
        else rdsu[sr.top().id]=sr.top().val;
        sr.pop();
    }
    timr--;
}

void pushfront(int x){
    for(int i=0;i<v[x].size();i++){
        if(v[x][i]>x)connectL(x,v[x][i]);
    }
}

void popfront(int x){
    for(int i=0;i<v[x].size();i++){
        if(v[x][i]>x)undoL();
    }
}

void pushback(int x){
    for(int i=0;i<v[x].size();i++){
        if(v[x][i]<x)connectR(x,v[x][i]);
    }
}

void popback(int x){
    for(int i=0;i<v[x].size();i++){
        if(v[x][i]<x)undoR();
    }
}

int check(int s,int e){
    for(int i=0;i<n;i++){
        if(rootL(i)==rootL(s) and rootR(i)==rootR(e))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){
    n=N; m=int(X.size()); q=int(S.size());
    ans.resize(q);
    
    for(int i=0;i<n;i++){
        ldsu[i]=rdsu[i]=i;
        lsz[i]=rsz[i]=1;
    }

    for(int i=1;i<=m;i++){
        a=X[i-1]; b=Y[i-1];
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(int i=0;i<=n;i++){
        bucket[i]=i/bucket_sz;
    }

    for(int i=0;i<q;i++){
        qs[i].s=S[i]; qs[i].e=E[i]; qs[i].l=L[i]; qs[i].r=R[i];
        qs[i].id=i;
    }
    sort(qs,qs+q);

    l=n; r=-1;
    for(int i=0;i<q;i++){
        while(l>qs[i].l){
            l--; pushfront(l);
        }
        while(l<qs[i].l){
            popfront(l); l++;
        }
        while(r<qs[i].r){
            r++; pushback(r);
        }
        while(r>qs[i].r){
            popback(r); r--;
        }
        ans[qs[i].id]=check(qs[i].s,qs[i].e);
    }

    return ans;
}

Compilation message (stderr)

werewolf.cpp: In function 'void pushfront(int)':
werewolf.cpp:86:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
werewolf.cpp: In function 'void popfront(int)':
werewolf.cpp:92:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
werewolf.cpp: In function 'void pushback(int)':
werewolf.cpp:98:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
werewolf.cpp: In function 'void popback(int)':
werewolf.cpp:104:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~

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