Submission #710516

#	Time	Username	Problem	Language	Result	Execution time	Memory
710516		rrrr10000	Werewolf (IOI18_werewolf)	C++14	100 / 100	727 ms	84188 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> P;
typedef vector<P> vp;
typedef vector<vp> vvp;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define pb emplace_back
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
template<class T> void outvv(T v){for(auto x:v)outv(x);}
template<class T> void outvp(T v){rep(i,v.size()){cout<<'('<<v[i].fi<<','<<v[i].se<<')';}cout<<endl;}
template<class T> void outvvp(T v){for(auto x:v)outvp(x);}

vector<int> check_validity(int N,vector<int> X,vector<int> Y,vector<int> S,vector<int> E,vector<int> L,vector<int> R){
    ll M=X.size(),Q=L.size();
    vvi ord(2);
    vvp rng(2,vp(Q));
    vector<int> ans(Q);
    {
        vvi edge(N),query(N);
        vi par(N,-1),data(N,-1),lca(Q);
        rep(i,M)edge[min(X[i],Y[i])].pb(i);
        rep(i,Q)query[L[i]].pb(i);
        auto root=[&](auto && self, ll i) -> ll {
            if(data[i]==-1)return i;
            data[i]=self(self,data[i]);
            return data[i];
        };
        for(int i=N-1;i>=0;i--){
            for(ll x:edge[i]){
                ll a=root(root,X[x]),b=root(root,Y[x]);
                if(a!=b){
                    if(a<b)swap(a,b);
                    par[a]=data[a]=b;
                }
            }
            for(ll x:query[i]){
                lca[x]=root(root,S[x]);
            }
        }
        vvi ch(N);
        rep(i,N)if(par[i]!=-1)ch[par[i]].pb(i);
        ll cnt=0;
        vp euler(N);
        auto dfs=[&](auto && self, ll i) -> void {
            ord[0].pb(i);
            euler[i].fi=cnt++;
            for(ll x:ch[i])self(self,x);
            euler[i].se=cnt;
        };dfs(dfs,0);
        rep(i,Q)rng[0][i]=euler[lca[i]];
    }
    {
        vvi edge(N),query(N);
        vi par(N,-1),data(N,-1),lca(Q);
        rep(i,M)edge[max(X[i],Y[i])].pb(i);
        rep(i,Q)query[R[i]].pb(i);
        auto root=[&](auto && self, ll i) -> ll {
            if(data[i]==-1)return i;
            data[i]=self(self,data[i]);
            return data[i];
        };
        rep(i,N){
            for(ll x:edge[i]){
                ll a=root(root,X[x]),b=root(root,Y[x]);
                if(a!=b){
                    if(a>b)swap(a,b);
                    par[a]=data[a]=b;
                }
            }
            for(ll x:query[i]){
                lca[x]=root(root,E[x]);
            }
        }
        vvi ch(N);
        rep(i,N)if(par[i]!=-1)ch[par[i]].pb(i);
        ll cnt=0;
        vp euler(N);
        auto dfs=[&](auto && self, ll i) -> void {
            ord[1].pb(i);
            euler[i].fi=cnt++;
            for(ll x:ch[i])self(self,x);
            euler[i].se=cnt;
        };dfs(dfs,N-1);
        rep(i,Q)rng[1][i]=euler[lca[i]];
    }
    vvi ins(N);
    rep(i,Q)ins[rng[0][i].fi].pb(i);
    vi rv(N);
    rep(i,N)rv[ord[1][i]]=i;
    vvi seg(N*2);
    rep(i,N){
        for(ll x:ins[i]){
            ll l=rng[1][x].fi,r=rng[1][x].se;
            for(l+=N,r+=N;l<r;l>>=1,r>>=1){
                if(l&1)seg[l++].pb(x);
                if(r&1)seg[--r].pb(x);
            }
        }
        for(ll j=rv[ord[0][i]]+N;j>0;j>>=1){
            for(ll x:seg[j])if(rng[0][x].se>i){
                ans[x]=1;
            }
            seg[j].clear();
        }
    }
    return ans;
}

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