Submission #401333

#	Time	Username	Problem	Language	Result	Execution time	Memory
401333		Osama_Alkhodairy	Werewolf (IOI18_werewolf)	C++17	100 / 100	882 ms	121720 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"
//~ #include "grader.cpp"
using namespace std;

const int N = 400001;

struct dsu{
    int n, p[N], l[N], r[N], t;
    vector <int> v[N], perm;
    void resize(int _n){
        n = _n;
        t = 0;
        for(int i = 0 ; i < 2 * n ; i++){
            p[i] = i;
        }
    }
    int find(int x){
        if(p[x] == x) return x;
        return p[x] = find(p[x]);
    }
    void merge(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return;
        v[n].push_back(x);
        v[n].push_back(y);
        p[x] = n;
        p[y] = n;
        n++;
    }
    void dfs(int node){
        perm.push_back(node);
        l[node] = t++;
        for(auto &i : v[node]){
            dfs(i);
        }
        r[node] = t - 1;
    }
    void dfs(){
        dfs(n - 1);
    }
};

struct segment{
    int n, tree[2 * N];
    void resize(int _n){
        n = _n;
    }
    void update(int p, int v){
        for(tree[p += n] = v ; p > 1 ; p >>= 1){
            tree[p >> 1] = tree[p] + tree[p ^ 1];
        }
    }
    int query(int l, int r){
        r++;
        int ret = 0;
        for(l += n, r += n ; l < r ; l >>= 1, r >>= 1){
            if(l & 1) ret += tree[l++];
            if(r & 1) ret += tree[--r];
        }
        return ret;
    }
};

vector <int> v[N], g[N];
vector <pair <int, int> > q, h[N];
dsu a, b;
segment tree;

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
    a.resize(N);
    b.resize(N);
    int M = X.size(), Q = S.size();
    for(int i = 0 ; i < M ; i++){
        v[X[i]].push_back(Y[i]);
        v[Y[i]].push_back(X[i]);
    }
    q.resize(S.size());
    for(int i = 0 ; i < Q ; i++){
        g[L[i]].push_back(i);
    }
    for(int i = N - 1 ; i >= 0 ; i--){
        for(auto &j : v[i]){
            if(j > i){
                a.merge(i, j);
            }
        }
        for(auto &j : g[i]){
            q[j].first = a.find(S[j]);
        }
        g[i].clear();
    }
    for(int i = 0 ; i < Q ; i++){
        g[R[i]].push_back(i);
    }
    for(int i = 0 ; i < N ; i++){
        for(auto &j : v[i]){
            if(j < i){
                b.merge(i, j);
            }
        }
        for(auto &j : g[i]){
            q[j].second = b.find(E[j]);
        }
        g[i].clear();
    }
    a.dfs();
    b.dfs();
    vector <int> pos(2 * N - 1);
    for(int i = 0 ; i < 2 * N - 1 ; i++){
        pos[b.perm[i]] = i;
    }
    tree.resize(2 * N - 1);
    for(int i = 0 ; i < Q ; i++){
        h[a.r[q[i].first]].push_back(make_pair(i, 1));
        if(a.l[q[i].first] > 0){
            h[a.l[q[i].first] - 1].push_back(make_pair(i, -1));
        }
    }
    vector <int> ans(Q);
    for(int i = 0 ; i < 2 * N - 1 ; i++){
        if(a.perm[i] < N) tree.update(pos[a.perm[i]], 1);
        for(auto &j : h[i]){
            ans[j.first] += tree.query(b.l[q[j.first].second], b.r[q[j.first].second]) * j.second;
        }
    }
    for(auto &i : ans) i = i > 0;
    return ans;
}

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