Submission #805458

#	Time	Username	Problem	Language	Result	Execution time	Memory
805458		Khizri	Werewolf (IOI18_werewolf)	C++17	100 / 100	1114 ms	276172 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
const int mxn=2e6+5;
int n,m,q,tmm,nxt=1,mn[mxn],mx[mxn],p[mxn],sz[mxn],idx[mxn],idx2[mxn],l[mxn],r[mxn],l2[mxn],r2[mxn],L[mxn*20],R[mxn*20],room[mxn],tree[mxn*20],par[mxn][20],par2[mxn][20];
vector<int>vt[mxn];
vector<int>vtx[mxn],vty[mxn];
void build(int node,int l,int r){
    if(l==r) return;
    L[node]=++nxt;
    R[node]=++nxt;
    int m=(l+r)/2;
    build(L[node],l,m);
    build(R[node],m+1,r);
}
int update(int node,int l,int r,int pos){
    int nw=++nxt;
    if(l==r){
        tree[nw]=1;
        return nw;
    }
    int m=(l+r)/2;
    L[nw]=L[node],R[nw]=R[node];
    if(pos<=m){
        L[nw]=update(L[nw],l,m,pos);
    }
    else{
        R[nw]=update(R[nw],m+1,r,pos);
    }
    tree[nw]=tree[L[nw]]+tree[R[nw]];
    return nw;
}
int query(int node,int node2,int l,int r,int ql,int qr){
    if(l>qr||r<ql){
        return 0;
    }
    if(ql<=l&&r<=qr){
        return tree[node]-tree[node2];
    }
    int m=(l+r)/2;
    return query(L[node],L[node2],l,m,ql,qr)+query(R[node],R[node2],m+1,r,ql,qr);
}
void dfs(int u,int p){
    par[u][0]=p;
    l[u]=++tmm;
    idx[tmm]=u;
    for(int v:vtx[u]){
        if(v!=p){
            dfs(v,u);
        }
    }
    r[u]=tmm;
}
void dfs2(int u,int p){
    par2[u][0]=p;
    l2[u]=++tmm;
    idx2[tmm]=u;
    for(int v:vty[u]){
        if(v!=p){
            dfs2(v,u);
        }
    }
    r2[u]=tmm;
}
int fnd(int u){
    if(p[u]==u) return u;
    return p[u]=fnd(p[u]);
}
void Union(int u,int v){
    u=fnd(u);
    v=fnd(v);
    if(u!=v){
        if(sz[v]>sz[u]) swap(u,v);
        sz[u]+=sz[v];
        p[v]=u;
        mn[u]=min(mn[u],mn[v]);
        mx[u]=max(mx[u],mx[v]);
    }
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> lx,vector<int> rx) {
    q = S.size();
    n=N;
    m=X.size();
    for(int i=0;i<m;i++){
        int u=X[i]+1,v=Y[i]+1;
        vt[u].pb(v);
        vt[v].pb(u);
    }
    for(int i=1;i<=n;i++){
        p[i]=i;
        sz[i]=1;
        mx[i]=i;
        mn[i]=i;
    }
    for(int i=n;i>=1;i--){
        int u=i;
        for(int v:vt[u]){
            if(v>u&&fnd(u)!=fnd(v)){
                int nw=mn[fnd(v)];
                vtx[u].pb(nw);
                vtx[nw].pb(u);
                Union(u,nw);
            }
        }
    }
    for(int i=1;i<=n;i++){
        p[i]=i;
        sz[i]=1;
        mx[i]=i;
        mn[i]=i;
    }
    for(int i=1;i<=n;i++){
        int u=i;
        for(int v:vt[u]){
            if(v<u&&fnd(v)!=fnd(u)){
                int nw=mx[fnd(v)];
                vty[u].pb(nw);
                vty[nw].pb(u);
                Union(u,nw);
            }
        }
    }
    tmm=0;
    dfs(1,-1);
    par[1][0]=1;
    tmm=0;
    dfs2(n,-1);
    par2[n][0]=n;
    for(int j=1;j<20;j++){
        for(int i=1;i<=n;i++){
            par[i][j]=par[par[i][j-1]][j-1];
            par2[i][j]=par2[par2[i][j-1]][j-1];
        }
    }
    build(1,1,n);
    room[0]=1;
    for(int i=1;i<=n;i++){
        int a=idx2[i];
        int pos=l[a];
        room[i]=update(room[i-1],1,n,pos);
    }
    vector<int>ans;
    for(int i=0;i<q;i++){
        int u=S[i]+1,v=E[i]+1,a=lx[i],b=rx[i];
        for(int j=19;j>=0;j--){
            if(par[u][j]-1>=a){
                u=par[u][j];
            }
            if(par2[v][j]-1<=b){
                v=par2[v][j];
            }
        }
        if(query(room[r2[v]],room[l2[v]-1],1,n,l[u],r[u])>0){
            ans.pb(1);
        }
        else{
            ans.pb(0);
        }
    }
    return ans;
}

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