oj.uz

Submission #824989

# Submission time Handle Problem Language Result Execution time Memory
824989 2023-08-14T12:54:52 Z phoenix Werewolf (IOI18_werewolf) C++17
100 / 100
 522 ms 87852 KB 
#include<bits/stdc++.h>
#include "werewolf.h"

using namespace std;

struct SegTree {
    const static int N = (1 << 18);
    vector<int> t;
    SegTree() {
        t.assign(2 * N, -1);
    }
    void update(int pos, int val) {
        for(t[pos += N] = val; pos > 1; pos >>= 1) {
            t[pos >> 1] = max(t[pos], t[(pos ^ 1)]);
        }
    }
    int get(int ql, int qr) {
        int res = -1;
        for(ql += N, qr += N + 1; ql < qr; ql >>= 1, qr >>= 1) {
            if(ql & 1) res = max(t[ql++], res);
            if(qr & 1) res = max(t[--qr], res);
        }
        return res;
    }
};

struct DSU {
    vector<int> p, r;
    DSU(int n) {
        p.assign(n, 0);
        r.assign(n, 1);
        iota(p.begin(), p.end(), 0);
    }
    int find(int x) {
        return p[x] = (p[x] == x ? x : find(p[x]));
    }
    void merge(int u, int v) {
        u = find(u);
        v = find(v);
        if(u == v) return;
        p[v] = u;
    }
};
const int N = 200010;

struct Tree {
    vector<int> g[N];
    vector<int> order;
    int tin[N], tout[N], anc[N][18];

    void dfs(int s, int p) {
        tin[s] = (int)order.size();
        order.push_back(s);
        anc[s][0] = p;
        for(int i = 1; i < 18; i++) 
            anc[s][i] = anc[anc[s][i - 1]][i - 1];
            
        for(int to : g[s]) {
            if(to == p) continue;
            dfs(to, s);
        }
        tout[s] = (int)order.size() - 1;
    }
};

Tree LL, RR;
vector<int> g[N];
SegTree st;

vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                  vector<int> S, vector<int> T,
                                  vector<int> L, vector<int> R) {
    int m = (int)X.size(), q = (int)S.size();
    for(int i = 0; i < m; i++) {
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }
    DSU ds(N);
    for(int i = 0; i < N; i++) {
        for(int to : g[i]) {
            to = ds.find(to);
            if(to >= i) continue;
            ds.merge(i, to);
            RR.g[i].push_back(to);
        }
    }
    ds = DSU(N);
    for(int i = N - 1; i >= 0; i--) {
        for(int to : g[i]) {
            to = ds.find(to);
            if(to <= i) continue;
            ds.merge(i, to);
            LL.g[i].push_back(to);
        }
    }
    LL.dfs(0, 0);
    RR.dfs(N - 1, N - 1);
    vector<int> qr[N];
    vector<int> res(q);

    for(int i = 0; i < q; i++) {
        for(int k = 17; k >= 0; k--) {
            if(LL.anc[S[i]][k] >= L[i]) 
                S[i] = LL.anc[S[i]][k];
            if(RR.anc[T[i]][k] <= R[i])
                T[i] = RR.anc[T[i]][k];
        }
        qr[LL.tout[S[i]]].push_back(i);
    }
    for(int i = 0; i < N; i++) {
        int x = LL.order[i];
        st.update(RR.tin[x], i);
        for(int query : qr[i]) {
            int l = RR.tin[T[query]], r = RR.tout[T[query]];
            res[query] = (st.get(l, r) >= LL.tin[S[query]]); 
        }
    }   
    return res;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16468 KB Output is correct
2 Correct 9 ms 16468 KB Output is correct
3 Correct 9 ms 16472 KB Output is correct
4 Correct 9 ms 16476 KB Output is correct
5 Correct 9 ms 16468 KB Output is correct
6 Correct 9 ms 16468 KB Output is correct
7 Correct 9 ms 16440 KB Output is correct
8 Correct 8 ms 16468 KB Output is correct
9 Correct 8 ms 16468 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16468 KB Output is correct
2 Correct 9 ms 16468 KB Output is correct
3 Correct 9 ms 16472 KB Output is correct
4 Correct 9 ms 16476 KB Output is correct
5 Correct 9 ms 16468 KB Output is correct
6 Correct 9 ms 16468 KB Output is correct
7 Correct 9 ms 16440 KB Output is correct
8 Correct 8 ms 16468 KB Output is correct
9 Correct 8 ms 16468 KB Output is correct
10 Correct 12 ms 17508 KB Output is correct
11 Correct 12 ms 17492 KB Output is correct
12 Correct 12 ms 17548 KB Output is correct
13 Correct 15 ms 17596 KB Output is correct
14 Correct 12 ms 17616 KB Output is correct
15 Correct 13 ms 17616 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 82648 KB Output is correct
2 Correct 381 ms 81996 KB Output is correct
3 Correct 351 ms 81948 KB Output is correct
4 Correct 347 ms 82080 KB Output is correct
5 Correct 340 ms 82060 KB Output is correct
6 Correct 369 ms 82548 KB Output is correct
7 Correct 377 ms 82248 KB Output is correct
8 Correct 370 ms 82092 KB Output is correct
9 Correct 358 ms 82020 KB Output is correct
10 Correct 281 ms 81828 KB Output is correct
11 Correct 290 ms 81936 KB Output is correct
12 Correct 323 ms 81980 KB Output is correct
13 Correct 420 ms 86344 KB Output is correct
14 Correct 415 ms 86388 KB Output is correct
15 Correct 419 ms 86228 KB Output is correct
16 Correct 416 ms 86228 KB Output is correct
17 Correct 389 ms 82360 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16468 KB Output is correct
2 Correct 9 ms 16468 KB Output is correct
3 Correct 9 ms 16472 KB Output is correct
4 Correct 9 ms 16476 KB Output is correct
5 Correct 9 ms 16468 KB Output is correct
6 Correct 9 ms 16468 KB Output is correct
7 Correct 9 ms 16440 KB Output is correct
8 Correct 8 ms 16468 KB Output is correct
9 Correct 8 ms 16468 KB Output is correct
10 Correct 12 ms 17508 KB Output is correct
11 Correct 12 ms 17492 KB Output is correct
12 Correct 12 ms 17548 KB Output is correct
13 Correct 15 ms 17596 KB Output is correct
14 Correct 12 ms 17616 KB Output is correct
15 Correct 13 ms 17616 KB Output is correct
16 Correct 406 ms 82648 KB Output is correct
17 Correct 381 ms 81996 KB Output is correct
18 Correct 351 ms 81948 KB Output is correct
19 Correct 347 ms 82080 KB Output is correct
20 Correct 340 ms 82060 KB Output is correct
21 Correct 369 ms 82548 KB Output is correct
22 Correct 377 ms 82248 KB Output is correct
23 Correct 370 ms 82092 KB Output is correct
24 Correct 358 ms 82020 KB Output is correct
25 Correct 281 ms 81828 KB Output is correct
26 Correct 290 ms 81936 KB Output is correct
27 Correct 323 ms 81980 KB Output is correct
28 Correct 420 ms 86344 KB Output is correct
29 Correct 415 ms 86388 KB Output is correct
30 Correct 419 ms 86228 KB Output is correct
31 Correct 416 ms 86228 KB Output is correct
32 Correct 389 ms 82360 KB Output is correct
33 Correct 455 ms 82504 KB Output is correct
34 Correct 191 ms 37944 KB Output is correct
35 Correct 447 ms 82880 KB Output is correct
36 Correct 443 ms 82796 KB Output is correct
37 Correct 446 ms 82728 KB Output is correct
38 Correct 437 ms 82968 KB Output is correct
39 Correct 450 ms 86060 KB Output is correct
40 Correct 522 ms 87852 KB Output is correct
41 Correct 388 ms 81856 KB Output is correct
42 Correct 350 ms 82608 KB Output is correct
43 Correct 473 ms 84832 KB Output is correct
44 Correct 413 ms 82148 KB Output is correct
45 Correct 379 ms 85168 KB Output is correct
46 Correct 392 ms 84920 KB Output is correct
47 Correct 407 ms 86676 KB Output is correct
48 Correct 424 ms 86220 KB Output is correct
49 Correct 414 ms 86220 KB Output is correct
50 Correct 414 ms 86616 KB Output is correct
51 Correct 457 ms 87364 KB Output is correct
52 Correct 468 ms 87288 KB Output is correct