Submission #987401

#	Time	Username	Problem	Language	Result	Execution time	Memory
987401		yeediot	Werewolf (IOI18_werewolf)	C++17	100 / 100	1281 ms	97100 KiB

werewolf

#pragma GCC optimize("O2")
#include<bits/stdc++.h>
#include "werewolf.h"
using namespace std;
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define vi vector<int>
#define why_TOI_is_so_de ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int mxn=2e5+5;
int n;
vector<int>adj2[mxn];
struct DSU{
    int to[mxn];
    void init(){
        for(int i=0;i<=n;i++){
            to[i]=i;
        }
    }
    int find(int x){
        return x==to[x]?x:to[x]=find(to[x]);
    }
}d;
struct tree{
    vector<vector<int>>adj,jump;
    int flg, timer, in[mxn], out[mxn], ord[mxn];
    void init(int f){
        adj.resize(n+1);
        flg=f;
        jump.resize(20,vector<int>(n+1));
    }
    void dfs(int v,int pa){
        in[v]=++timer;
        ord[timer]=v;
        jump[0][v]=pa;
        for(auto u:adj[v]){
            if(u!=pa)dfs(u,v);
        }
        out[v]=timer;
    }
    void build(){
        for(int i=1;i<20;i++){
            for(int j=1;j<=n;j++){
                jump[i][j]=jump[i-1][jump[i-1][j]];
            }
        }
    }
    int find(int st,int x){
        if(flg){
            for(int i=19;i>=0;i--){
                if(jump[i][st]<=x){
                    st=jump[i][st];
                }
            }
        }
        else{
            for(int i=19;i>=0;i--){
                if(jump[i][st]>=x){
                    st=jump[i][st];
                }
            }
        }
        return st;
    }
}mn, mx;
vector<int>upd(mxn),ans;
vector<pair<int,int>>in[mxn];
int bit[mxn];
void modify(int p){
    for(;p<=n;p+=p&-p){
        bit[p]++;
    }
}
int query(int p){
    int res=0;
    for(;p;p-=p&-p){
        res+=bit[p];
    }
    return res;
}
vi check_validity(int N,vi X,vi Y,vi S,vi E,vi L,vi R){
    why_TOI_is_so_de;
    n=N;
    ans.resize(sz(E));
    for(int i=0;i<sz(X);i++){
        int a=X[i],b=Y[i];
        a++;
        b++;
        adj2[a].pb(b);
        adj2[b].pb(a);
    }
    mn.init(1);
    mx.init(0);
    d.init();
    for(int x=n;x>=1;x--){
        for(auto y:adj2[x]){
            if(y<x)continue;
            int fx=d.find(y),fy=d.find(x);
            if(fx==fy)continue;
            mx.adj[fy].pb(fx);
            d.to[fx]=fy;
        }
    }
    d.init();
    for(int x=1;x<=n;x++){
        for(auto y:adj2[x]){
            if(y>x)continue;
            int fx=d.find(y),fy=d.find(x);
            if(fx==fy)continue;
            mn.adj[fy].pb(fx);
            d.to[fx]=fy;
        }
    }
    mn.dfs(n,n);
    mx.dfs(1,1);
    mn.build();
    mx.build();
    for(int i=1;i<=n;i++){
        upd[i]=mn.in[mx.ord[i]];
    }
    for(int i=0;i<sz(S);i++){
        int s=S[i]+1,e=E[i]+1,l=L[i]+1,r=R[i]+1;
        int fs=mx.find(s,l),se=mn.find(e,r);
        S[i]=se;
        in[mx.in[fs]-1].pb({i,-1});
        in[mx.out[fs]].pb({i,1});
    }
    for(int i=1;i<=n;i++){
        modify(upd[i]);
        for(auto [id,flg]:in[i]){
            ans[id]+=flg*(query(mn.out[S[id]])-query(mn.in[S[id]]-1));
            if(flg==1 and ans[id])ans[id]=1;
        }
    }
    return ans;
}

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