Submission #1268313

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268313		Bui_Quoc_Cuong	Werewolf (IOI18_werewolf)	C++20	100 / 100	414 ms	107964 KiB

werewolf

#include <bits/stdc++.h>
using namespace std;    
const int maxn = 2e5 + 5;
int n, m, q;
int X[maxn], Y[maxn], S[maxn], E[maxn], L[maxn], R[maxn]; 
vector <int> g[maxn];
vector <int> adj[maxn][2];
struct DisjointSet{
    int par[maxn], root;
    void init(){
        for(int i = 1; i <= n; i++){
            par[i] = i;
        }
    }
    int find(int i){
        return par[i] == i ? i : par[i] = find(par[i]);
    }
    bool joint(int u, int v, int t){
        int x = find(u), y = find(v);
        if(x == y) return 0;
        adj[x][t].push_back(y);
        root = x;
        par[y] = x;
        return 1;
    }
} DSU0, DSU1;   
int tin[maxn][2], tout[maxn][2], timedfs, jump[maxn][20][2], arr[maxn][2];
void dfs(int u, int t){
    tin[u][t] = ++ timedfs;
    arr[timedfs][t] = u;
    for(int &v : adj[u][t]){
        jump[v][0][t] = u;
        for(int j = 1; (1 << j) <= n; j++){
            jump[v][j][t] = jump[jump[v][j - 1][t]][j - 1][t];
        }
        dfs(v, t);
    }
    tout[u][t] = timedfs;
}
vector <array <int, 4>> ask[maxn];
int bit[maxn];
void up(int u, int val){
    for(int i = u; i <= n; i+= i&-i) bit[i]+= val;
}
int get(int u){
    int sum = 0;
    for(int i = u; i; i-= i&-i) sum+= bit[i];
    return sum;
}
vector <int> check_validity(int N, vector <int> X, vector <int> Y, vector <int> S, vector <int> E, vector <int> L, vector <int> R){
    n = N;
    q = S.size();
    m = X.size();
    vector <int> ans(q, 0);
    for(int i = 0; i < m; i++){
        // cin >> X[i];
        X[i]++;
    }
    for(int i = 0; i < m; i++){
        // cin >> Y[i];
        Y[i]++;
    }
    for(int i = 0; i < q; i++){
        // cin >> S[i];
        S[i]++;
    }
    for(int i = 0; i < q; i++){
        // cin >> E[i];
        E[i]++;
    }
    for(int i = 0; i < q; i++){
        // cin >> L[i];
        L[i]++;
    }
    for(int i = 0; i < q; i++){
        // cin >> R[i];
        R[i]++;
    }
    for(int i = 0; i < m; i++){
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }
    DSU0.init();
    DSU1.init();
    for(int i = 1; i <= n; i++){
        for(int j : g[i]) if(j < i){
            DSU0.joint(i, j, 0);
        }
    }
    for(int i = n; i >= 1; i--){
        for(int j : g[i] ) if(j > i){
            DSU1.joint(i, j, 1);
        }
    }
    timedfs = 0;
    dfs(DSU0.root, 0);
    timedfs = 0;
    dfs(DSU1.root, 1);
    for(int i = 0; i < q; i++){
        int l = L[i], r = R[i], s = S[i], t = E[i];
        int z = __lg(n);
        for(int ss = z; ss >= 0; ss--){
            if(jump[s][ss][1] >= l) s = jump[s][ss][1];
            if(jump[t][ss][0] <= r && jump[t][ss][0] != 0) t = jump[t][ss][0];
        }
        ask[tout[t][0]].push_back({tin[s][1], tout[s][1], i, 1});
        ask[tin[t][0] - 1].push_back({tin[s][1], tout[s][1], i, - 1});
    }
    for(int j = 1; j <= n; j++){
        up(tin[arr[j][0]][1], 1);
        for(auto it : ask[j]){
            ans[it[2]]+= it[3] * (get(it[1]) - get(it[0] - 1));
        }
    }   
    for(int i = 0; i < q; i++){
        ans[i] = (ans[i] > 0);
    }
    return ans;
}
// int32_t main(){
//     ios_base::sync_with_stdio(0); cin.tie(0); 
//     #define koa "kieuoanh"
//     if(fopen(koa".inp", "r")){
//         freopen(koa".inp", "r", stdin); freopen(koa".out", "w", stdout);
//     }
//     cin >> n >> m >> q;
//     for(int i = 1; i <= m; i++){
//         cin >> X[i];
//         X[i]++;
//     }
//     for(int i = 1; i <= m; i++){
//         cin >> Y[i];
//         Y[i]++;
//     }
//     for(int i = 1; i <= q; i++){
//         cin >> S[i];
//         S[i]++;
//     }
//     for(int i = 1; i <= q; i++){
//         cin >> E[i];
//         E[i]++;
//     }
//     for(int i = 1; i <= q; i++){
//         cin >> L[i];
//         L[i]++;
//     }
//     for(int i = 1; i <= q; i++){
//         cin >> R[i];
//         R[i]++;
//     }
//     for(int i = 1; i <= m; i++){
//         g[X[i]].push_back(Y[i]);
//         g[Y[i]].push_back(X[i]);
//     }
//     DSU0.init();
//     DSU1.init();
//     for(int i = 1; i <= n; i++){
//         for(int j : g[i]) if(j < i){
//             DSU0.joint(i, j, 0);
//         }
//     }
//     for(int i = n; i >= 1; i--){
//         for(int j : g[i] ) if(j > i){
//             DSU1.joint(i, j, 1);
//         }
//     }
//     timedfs = 0;
//     dfs(DSU0.root, 0);
//     timedfs = 0;
//     dfs(DSU1.root, 1);
//     for(int i = 1; i <= q; i++){
//         int l = L[i], r = R[i], s = S[i], t = E[i];
//         int z = __lg(n);
//         for(int ss = z; ss >= 0; ss--){
//             if(jump[s][ss][1] >= l) s = jump[s][ss][1];
//             if(jump[t][ss][0] <= r && jump[t][ss][0] != 0) t = jump[t][ss][0];
//         }
//         ask[tout[t][0]].push_back({tin[s][1], tout[s][1], i, 1});
//         ask[tin[t][0] - 1].push_back({tin[s][1], tout[s][1], i, - 1});
//     }
//     for(int j = 1; j <= n; j++){
//         up(tin[arr[j][0]][1], 1);
//         for(auto it : ask[j]){
//             ans[it[2]]+= it[3] * (get(it[1]) - get(it[0] - 1));
//         }
//     }   
//     for(int i = 1; i <= q; i++){
//         cout << (ans[i] > 0) << "\n";
//     }
//     return 0;
// }

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