Submission #1165842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165842		TsotneSV	Werewolf (IOI18_werewolf)	C++17	100 / 100	773 ms	137352 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
/*⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⠀⠀⠀⠀⠀⠀⠀⡄⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⣿⠛⣿⠀⠀⠀⠀⣤⣿⢻⡇⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⣿⡛⠀⣤⣿⣿⣤⣤⣿⣿⣤⢸⡇⠀
⠀⠀⠀⠀⠀⠀⠀⠀⣴⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠀
⠀⠀⠀⠀⠀⠀⠀⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡗⠀
⢠⣼⣿⣿⣿⣿⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷
⢸⣿⣿⡟⠛⠛⢿⣿⣿⣿⣿⣿⣿⣿⣤⣤⣤⣿⣿⣿⣿⣤⣤⣼⣿⣿
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠛⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⠋       
*/
#define fi first
#define se second
#define pb push_back
#define ins insert
#define sz(a) (int)(a.size())
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}

#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#include "debug.h"
#else
#define debug(...)
#endif

const int LG = 18; 

struct DSU {

    vector<int> parent,SIZE;

    DSU(int n) {
        parent.resize(n);
        SIZE.resize(n);
        for(int i=0;i<n;i++) {
            parent[i] = i;
            SIZE[i] = 1;
        }
    }

    int find_set(int u) {
        if(u == parent[u]) return u;
        return parent[u] = find_set(parent[u]);
    }

    void union_sets(int u,int v) {
        u = find_set(u);
        v = find_set(v);

        SIZE[u] += SIZE[v];
        parent[v] = u;
    }

};

vector<int> tree1(int n,vector<vector<int>> &g,vi &in,vi &out,vi &par) {

    in.resize(n); out.resize(n);

    DSU d(n); vector<vector<int>> g1(n);

    for(int i=n-1;i>=0;i--) {
        
        for(int u : g[i]) {
            if(u < i or d.find_set(u) == i) continue;
            u = d.find_set(u);
            d.union_sets(i,u);
            g1[i].pb(u);
            par[u] = i;
        }

    } 

    vector<int> tour; int timer = -1;

    function<void(int)> dfs = [&](int u) {
        in[u] = ++timer;
        tour.pb(u);

        for(int i : g1[u]) {
            dfs(i);
        } out[u] = timer;

    }; dfs(0);

    return tour;

}

vector<int> tree2(int n,vector<vector<int>> &g,vi &in,vi &out,vi &par) {

    in.resize(n); out.resize(n);

    DSU d(n); vector<vector<int>> g2(n);

    for(int i=0;i<n;i++) {
        
        for(int u : g[i]) {
            if(u > i or d.find_set(u) == i) continue;
            u = d.find_set(u);
            d.union_sets(i,u);
            g2[i].pb(u);
            par[u] = i;
        }

    } 

  
    vector<int> tour; int timer = -1;

    function<void(int)> dfs = [&](int u) {
        in[u] = ++timer;
        tour.pb(u);

        for(int i : g2[u]) {
            dfs(i);
        } out[u] = timer;

    }; dfs(n-1);

    return tour;

}

void transform1(int &S,int L,vector<vector<int>> &jmp) {

    for(int i=LG-1;i>=0;i--) {
        if(jmp[S][i] >= L) {
            S = jmp[S][i];
        }
    }

}

void transform2(int &E,int R,vector<vector<int>> &jmp) {

    for(int i=LG-1;i>=0;i--) {
        if(jmp[E][i] <= R) {
            E = jmp[E][i];
        }
    }

}

template<typename Node>
struct Segtr {


    int s;
    vector<Node> tree;

    void build(int v,int tl,int tr,vector<int> &arr) {
        if(tl == tr) {
            tree[v] = Node(arr[tl]);
        }else {
            int tm = (tl + tr)/2;
            build(2*v,tl,tm,arr); build(2*v+1,tm+1,tr,arr);
            tree[v].merge(tree[2*v],tree[2*v+1]);
        }
    }

    bool ok(Node &v,int L,int R) {

        if(L > R) return 0;

        int n = v.srt.size();

        int l = 0,r = n - 1;

        while(l <= r) {
            int m = (l + r)/2;
            if(v.srt[m] > R) {
                r = m - 1;
            } else if(v.srt[m] < L) {
                l = m + 1;
            } else return 1;
        } 
        
        return 0;

    }

    bool check(int v,int l,int r,int tl,int tr,int L,int R) {
        if(l > r) return 0;
        else if(tl == l && tr == r) return ok(tree[v],L,R);
        int tm = (tl + tr)/2;
        bool lo = check(2*v,l,min(r,tm),tl,tm,L,R),hi = check(2*v+1,max(l,tm+1),r,tm+1,tr,L,R);
        return lo|hi;
    }

    Segtr(int n,vector<int> &arr) {
        s = n;
        tree.resize(4*n);
        build(1,0,n-1,arr);
    }

};

struct Node1 {
    vector<int> srt;

    void merge(Node1 &a,Node1 &b) {
        std::merge(all(a.srt),all(b.srt),back_inserter(srt));
    }

    Node1() {srt = {};}

    Node1(int a) {
        srt.clear();
        srt.pb(a);
    }

};


vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    
    vector<vector<int>> g(N),jmp1,jmp2; int M = X.size(),Q = S.size();
    
    vector<int> answer(Q,0); // *
    
    for(int i=0;i<M;i++) g[X[i]].pb(Y[i]),g[Y[i]].pb(X[i]);
    
    vector<int> in[2],out[2],par1(N,0),par2(N,N-1);

    vi tour1 = tree1(N,g,in[0],out[0],par1),tour2 = tree2(N,g,in[1],out[1],par2);

    jmp1 = vector<vi>(N,vi(LG,0));
    jmp2 = vector<vi>(N,vi(LG,N-1));
    
    for(int i=0;i<N;i++) {
        jmp1[i][0] = par1[i];
        for(int j=1;j<LG;j++) jmp1[i][j] = jmp1[jmp1[i][j-1]][j-1];
    }

    for(int i=N-1;i>=0;i--) {
        jmp2[i][0] = par2[i];
        for(int j=1;j<LG;j++) jmp2[i][j] = jmp2[jmp2[i][j-1]][j-1];
    }

    map<int,int> mp;

    for(int i = 0;i < N;i++) mp[tour1[i]] = i;
    for(int i = 0;i < N;i++) tour2[i] = mp[tour2[i]];

    Segtr<Node1> T(N,tour2);

    for(int i=0;i<Q;i++) {

        if(L[i] > S[i] or R[i] < E[i]) answer[i] = 0;
        else {
            transform1(S[i],L[i],jmp1); transform2(E[i],R[i],jmp2);
            answer[i] = T.check(1,in[1][E[i]],out[1][E[i]],0,N-1,in[0][S[i]],out[0][S[i]]);
        }   

    } return answer;

}

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