Submission #1263160

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263160		zhangspicyuwu	Werewolf (IOI18_werewolf)	C++20	0 / 100	481 ms	163372 KiB

werewolf

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
//#define int long long
#define ld long double
#define pb push_back
const int N=3e5+5,M=317;
int n,q,m,cnt,par[2*N],vala[2*N],valb[2*N],sta[2*N],ena[2*N],stb[2*N],enb[2*N],spta[2*N][20],sptb[2*N][20],arra[2*N],arrb[2*N],upd[2*N],fenwick[2*N];
int ans[N];
struct query{
    int u,val,i;
};
vector<query> event[2*N];
void update(int u){
    while(u<2*n){
        fenwick[u]++;
        u+=(u&-u);
    }
}
int get(int u){
    int ans=0;
    while(u){
        ans+=fenwick[u];
        u-=(u&-u);
    }
    return ans;
}
struct edge{
    int val,u,v;
};
bool operator < (edge a,edge b){
    return a.val<b.val;
}
bool operator > (edge a,edge b){
    return a.val>b.val;
}
int Find(int u){
    if(par[u]==u) return u;
    else return par[u]=Find(par[u]);
}
vector<edge> vmin,vmax;
vector<int> adja[2*N],adjb[2*N];
void buildtreemin(int u,int v,int val){
    u=Find(u); v=Find(v);
    if(u==v) return;
    cnt++; vala[cnt]=val;
    par[u]=par[v]=cnt;
    adja[cnt].push_back(u);
    adja[cnt].push_back(v);
}
void buildtreemax(int u,int v,int val){
    u=Find(u); v=Find(v);
    if(u==v) return;
    cnt++; valb[cnt]=val;
    par[u]=par[v]=cnt;
    adjb[cnt].push_back(u);
    adjb[cnt].push_back(v);
}
void dfsa(int u){
    sta[u]=++cnt;
    arra[cnt]=u;
    for(auto v:adja[u]){
        spta[v][0]=u;
        dfsa(v);
    }
    ena[u]=cnt;
}
void dfsb(int u){
    stb[u]=++cnt;
    arrb[cnt]=u;
    for(auto v:adjb[u]){
        sptb[v][0]=u;
        dfsb(v);
    }
    enb[u]=cnt;
}
vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    m=x.size(); q=S.size();
    vmin.clear(); vmax.clear();
    for(int i=0;i<m;i++){
        int u=x[i]+1,v=y[i]+1;
        vmin.push_back({min(u,v),u,v});
        vmax.push_back({max(u,v),u,v});
    }
    sort(vmin.begin(),vmin.end(),greater<edge>());
    sort(vmax.begin(),vmax.end());
    cnt=n;
    for(int i=1;i<=n;i++) vala[i]=valb[i]=i;
    for(int i=1;i<2*n;i++) par[i]=i;
    for(auto i:vmin){
        buildtreemin(i.u,i.v,i.val);
    }
    cnt=n;
    for(int i=1;i<2*n;i++) par[i]=i;
    for(auto i:vmax){
        buildtreemax(i.u,i.v,i.val);
    }
    spta[2*n-1][0]=sptb[2*n-1][0]=2*n-1;
    cnt=0;
    dfsa(2*n-1);
    cnt=0;
    dfsb(2*n-1);
    for(int j=1;j<20;j++){
        for(int i=1;i<2*n;i++){
            spta[i][j]=spta[spta[i][j-1]][j-1];
            sptb[i][j]=sptb[sptb[i][j-1]][j-1];
        }
    }
    for(int i=0;i<q;i++){
        int s=S[i],e=E[i],l=L[i],r=R[i]; 
        if(s<l || e>r) continue;
        for(int i=19;i>=0;i--){
            if(spta[s][i] != 0 && vala[spta[s][i]]>=l) s=spta[s][i];
        }
        for(int i=19;i>=0;i--){
            if(sptb[e][i] != 0 && valb[sptb[e][i]]<=r) e=sptb[e][i];
        }
        event[ena[s]].push_back({enb[e],1,i});
        event[sta[s]-1].push_back({enb[e],-1,i});
        event[ena[s]].push_back({stb[e]-1,-1,i});
        event[sta[s]-1].push_back({stb[e]-1,1,i});
    }
    for(int i=1;i<=n;i++){
        upd[sta[i]]=stb[i];
    }
    for(int i=1;i<2*n;i++){
        if(upd[i]){
            update(upd[i]);
        }
        for(auto j:event[i]){
            ans[j.i]+=get(j.u)*j.val;
        }
    }
    vector<int> res;
    for(int i=0;i<q;i++){
      res.push_back((ans[i]!=0));
    }
    return res;
}

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