Submission #608467

#	Time	Username	Problem	Language	Result	Execution time	Memory
608467		rrrr10000	Werewolf (IOI18_werewolf)	C++14	0 / 100	909 ms	147628 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
#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 pb emplace_back
#define fi first
#define se second
template<class T> void out(T a){cout<<a<<endl;}
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> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
const ll inf=1001001001001001001;

vector<int> check_validity(int n, vector<int> X, vector<int> Y,vector<int> S, vector<int> E,vector<int> L, vector<int> R) {
    int Q = S.size();
    vvi g(n);
    rep(i,X.size()){
        g[X[i]].pb(Y[i]);g[Y[i]].pb(X[i]);
    }
    vi parL(n,-1),parR(n,-1);
    vvi queryL(n),queryR(n);
    {
        vi pp(n,-1);
        function<ll(ll)> root=[&](ll i){
            if(pp[i]==-1)return i;
            pp[i]=root(pp[i]);
            return pp[i];
        };
        vvi tmp(n);
        rep(i,Q)tmp[L[i]].pb(i);
        for(int i=n-1;i>=0;i--){
            for(auto x:g[i])if(x>i){
                ll t=root(x);
                if(t!=i)parL[t]=pp[t]=i;
            }
            for(ll x:tmp[i])queryL[root(S[x])].pb(x);
        }
    }
    {
        vi pp(n,-1);
        function<ll(ll)> root=[&](ll i){
            if(pp[i]==-1)return i;
            pp[i]=root(pp[i]);
            return pp[i];
        };
        vvi tmp(n);
        rep(i,Q)tmp[R[i]].pb(i);
        rep(i,n){
            for(auto x:g[i])if(x<i){
                ll t=root(x);
                if(t!=i)parR[t]=pp[t]=i;
            }
            for(ll x:tmp[i])queryR[root(E[x])].pb(x);
        }
    }
    vvi gL(n),gR(n);
    rep(i,n)if(parL[i]!=-1)gL[parL[i]].pb(i);
    rep(i,n)if(parR[i]!=-1)gR[parR[i]].pb(i);
    ll cnt=0;
    vp euler(n);
    function<void(ll)> dfs0=[&](ll i){
        euler[i].fi=cnt++;
        for(ll x:gR[i])dfs0(x);
        euler[i].se=cnt;
    };dfs0(n-1);
    vp rng(Q);
    rep(i,n)for(auto x:queryR[i])rng[x]=euler[i];
    vector<set<ll>> dp(n);
    vector<int> ans(Q);
    // for(auto x:rng)cout<<x.fi<<' '<<x.se<<endl;
    // for(auto x:euler)cout<<x.fi<<' '<<x.se<<endl;
    function<void(ll)> dfs1=[&](ll i){
        dp[i].insert(euler[i].fi);
        for(ll x:gL[i]){
            dfs1(x);
            if(dp[i].size()<dp[x].size())swap(dp[i],dp[x]);
            for(ll y:dp[x])dp[i].insert(y);
        }
        for(auto x:queryL[i]){
            auto itr=dp[i].lower_bound(rng[x].fi);
            if(itr!=dp[i].end()&&*itr<=rng[x].se)ans[x]=1;
        }
    };dfs1(0);
    return ans;
}

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