Submission #1163282

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163282		PagodePaiva	Werewolf (IOI18_werewolf)	C++17	100 / 100	671 ms	123756 KiB

werewolf

#include<bits/stdc++.h>
#include "werewolf.h"

using namespace std;

const int N = 200010;
const int LOGN = 20;
vector <int> g[N];
vector <int> g1[N], g2[N];
int tmm;
int tin[N][2], tout[N][2];
int pai[N][LOGN][2];

struct DSU{
    int pai[N], sz[N];
    stack <int> s;
    DSU(){
        for(int i = 0;i < N;i++){
            pai[i] = i;
            sz[i] = 1;
        }
    }
    void clear(int n){
        for(int i = 0;i < n;i++){
            pai[i] = i;
            sz[i] = 1;
        }
    }
    int find(int x){
        return pai[x] = (x == pai[x] ? x : find(pai[x]));
    }
    void join(int a, int b){
        a = find(a);
        b = find(b);
        if(a == b) {
            return;
        }
        pai[a] = b;
        sz[b] += sz[a];
    }
} dsu;

void constructG1(int n){
    dsu.clear(n);
    for(int i = n-1;i >= 0;i--){
        for(auto x : g[i]){
            if(x < i) continue;
            if(dsu.find(x) == i) continue;
            g1[i].push_back(dsu.find(x));
            g1[dsu.find(x)].push_back(i);
            dsu.join(dsu.find(x), i);
        }
    }
}

void constructG2(int n){
    dsu.clear(n);
    for(int i = 0;i < n;i++){
        for(auto x : g[i]){
            if(x > i) continue;
            if(dsu.find(x) == i) continue;
            g2[i].push_back(dsu.find(x));
            g2[dsu.find(x)].push_back(i);
            dsu.join(dsu.find(x), i);
        }
    }
}

vector <int> v1, v2;

void dfs1(int v, int p){
    pai[v][0][0] = p;
    tin[v][0] = tmm;
    v1.push_back(v);
    tmm++;
    for(auto x : g1[v]){
        if(x == p) continue;
        dfs1(x, v);
    }
    tout[v][0] = tmm;
}

void dfs2(int v, int p){
    pai[v][0][1] = p;
    tin[v][1] = tmm;
    tmm++;
    v2.push_back(v);
    for(auto x : g2[v]){
        if(x == p) continue;
        dfs2(x, v);
    }
    tout[v][1] = tmm;
}

struct Segtree{
    int tree[4*N];
    int join(int a, int b){
        return max(a, b);
    }
    void build(int node, int l, int r){
        if(l == r){
            tree[node] = -1;
            return;
        }
        int mid = (l+r)/2;
        build(2*node, l, mid);
        build(2*node+1, mid+1, r);
        tree[node] = -1;
        return;
    }
    void update(int node, int l, int r, int pos, int val){
        if(l == r){
            tree[node] = val;
            return;
        }
        int mid = (l+r)/2;
        if(l <= pos and pos <= mid) update(2*node, l, mid, pos, val);
        else update(2*node+1, mid+1, r, pos, val);
        tree[node] = join(tree[2*node], tree[2*node+1]);
        return;
    }
    int query(int node, int l, int r, int tl, int tr){
        if(l > tr or tl > r) return 0;
        if(l <= tl and tr <= r) return tree[node];
        int mid = (tl+tr)/2;
        return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
    }
} seg;

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 m = X.size();
    for(int i = 0;i < m;i++){
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }
    constructG1(n);
    constructG2(n);
    tmm = 0;
    dfs1(0, 0);
    tmm = 0;
    dfs2(n-1, n-1);
    for(int bit = 1;bit < LOGN;bit++){
        for(int i = 0;i < n;i++){
            for(int j = 0;j < 2;j++){
                pai[i][bit][j] = pai[pai[i][bit-1][j]][bit-1][j];
            }
        }
    }
    for(int i = 0;i < n;i++){
        // cout << "vizinhos 1 de " << i << ": ";
        for(auto x : g1[i]){
            // cout << x << ' ';
        }
        // cout << '\n';
    }
    for(int i = 0;i < n;i++){
        // cout << "vizinhos 2 de " << i << ": ";
        for(auto x : g2[i]){
            // cout << x << ' ';
        }
        // cout << '\n';
    }
    vector <int> query[2];
    for(int i = 0;i < S.size();i++){
        int s = S[i], mn = L[i];
        if(s < L[i]){
            query[0].push_back(-1);
            continue;
        }
        for(int bit = LOGN-1;bit >= 0;bit--){
            if(pai[s][bit][0] >= mn) s = pai[s][bit][0];
        }
        query[0].push_back(s);
    }
    for(int i = 0;i < E.size();i++){
        int s = E[i], mn = R[i];
        if(s > mn){
            query[1].push_back(-1);
            continue;
        }
        for(int bit = LOGN-1;bit >= 0;bit--){
            if(pai[s][bit][1] <= mn) s = pai[s][bit][1];
        }
        query[1].push_back(s);
    }
    vector <array <int, 4>> v;
    map <array <int, 4>, int> responder;
    map <int, int> ans;
    for(int i = 0;i < query[0].size();i++){
        int s = query[0][i], e = query[1][i];
        // cout << s << ' ' << e << '\n';
        if(s == -1 or e == -1){
            ans[i] = 0;
            continue;
        }
        v.push_back({tout[s][0]-1, tin[s][0], tin[e][1], tout[e][1]-1});
        responder[{tout[s][0]-1, tin[s][0], tin[e][1], tout[e][1]-1}] = i;
    }
    sort(v.begin(), v.end());
    vector <pair <int, int>> comprimir;
    map <int, int> aux;
    for(int i = 0;i < v2.size();i++){
        aux[v2[i]] = i;
    }
    for(auto &x : v1){
        x = aux[x];
    }    int at = 0;
    seg.build(1, 1, n);
    for(auto [b, a, c, d] : v){
        // cout << a << ' ' << b << ' ' << c << ' ' << d << '\n';
        while(at <= b){
            seg.update(1, 1, n, v1[at]+1, at);
            at++;
        }
        int res = seg.query(1, c+1, d+1, 1, n);
        if(res < a) responder[{b, a, c, d}] = 0;
        else responder[{b, a, c, d}] = 1;
    }    
    //// cout << '\n';   
    vector <int> resp;
    for(int i = 0;i < query[0].size();i++){
        int s = query[0][i], e = query[1][i];
        if(s == -1 or e == -1){
            resp.push_back(0);
            continue;
        }
        resp.push_back(responder[{tout[s][0]-1, tin[s][0], tin[e][1], tout[e][1]-1}]);
    }
    return resp;
}

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