oj.uz

Submission #425585

# Submission time Handle Problem Language Result Execution time Memory
425585 2021-06-13T07:59:34 Z 79brue Werewolf (IOI18_werewolf) C++14
100 / 100
 1773 ms 193140 KB 
#include <bits/stdc++.h>
#include "werewolf.h"

using namespace std;

typedef long long ll;

struct unionFind{
    int par[400002], root[400002], idx[400002];
    vector<int> child[400002];
    int l[400002], r[400002], inCnt = 0;
    int sps[400002][20];
    int n;

    void init(int _n, int dfidx){
        n = _n - 1;
        for(int i=0; i<=n; i++) par[i] = root[i] = i, idx[i] = dfidx;
    }

    int find(int x){
        if(x==root[x]) return x;
        return root[x] = find(root[x]);
    }

    void merge(int x, int y, int z){
        int newNode = ++n;
        x = find(x), y = find(y);
        par[x] = root[x] = par[y] = root[y] = newNode;
        child[newNode].push_back(x);
        child[newNode].push_back(y);
        par[newNode] = root[newNode] = newNode;
        idx[newNode] = z;
    }

    void ss(int x){
        if(child[x].empty()){
            l[x] = r[x] = inCnt++;
            return;
        }
        l[x] = INT_MAX;
        for(auto y: child[x]){
            ss(y);
            l[x] = min(l[x], l[y]);
            r[x] = max(r[x], r[y]);
        }
    }

    void makeDB(){
        n++;
        par[n-1] = par[n] = n;
        for(int i=0; i<=n; i++) sps[i][0] = par[i];
        for(int d=1; d<20; d++) for(int i=0; i<=n; i++) sps[i][d] = sps[sps[i][d-1]][d-1];
    }
} t1, t2;

struct segTree{
    vector<int> tree[800002];
    void init(int i, int l, int r, int *A){
        if(l==r){
            tree[i].push_back(A[l]);
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m, A);
        init(i*2+1, m+1, r, A);
        tree[i].resize(tree[i*2].size() + tree[i*2+1].size());
        merge(tree[i*2].begin(), tree[i*2].end(), tree[i*2+1].begin(), tree[i*2+1].end(), tree[i].begin());
    }

    bool chk(int i, int l, int r, int s, int e, int s1, int e1){
        if(r<s || e<l) return false;
        if(s<=l && r<=e) return upper_bound(tree[i].begin(), tree[i].end(), e1) != lower_bound(tree[i].begin(), tree[i].end(), s1);
        int m = (l+r)>>1;
        return chk(i*2, l, m, s, e, s1, e1) || chk(i*2+1, m+1, r, s, e, s1, e1);
    }
} tree;

int n, m, q;
vector<bool> vec;
vector<int> link[200002];
int arr[200002];
vector<int> ans;

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;
    m = (int)X.size();
    q = S.size();
    for(int i=0; i<m; i++) link[X[i]].push_back(Y[i]), link[Y[i]].push_back(X[i]);

    t1.init(n, n);
    t2.init(n, -1);
    for(int i=n-1; i>=0; i--){
        for(auto y: link[i]){
            if(y<i) continue;
            if(t1.find(i) != t1.find(y)) t1.merge(i, y, i);
        }
    }
    for(int i=0; i<n; i++){
        for(auto y: link[i]){
            if(y>i) continue;
            if(t2.find(i) != t2.find(y)) t2.merge(i, y, i);
        }
    }

    t1.ss(t1.n);
    t2.ss(t2.n);
    for(int i=0; i<n; i++) arr[t1.l[i]] = t2.l[i];
    tree.init(1, 0, n-1, arr);

    t1.makeDB();
    t2.makeDB();

    for(int i=0; i<q; i++){
        int s = S[i], e = E[i], l = L[i], r = R[i];
        int x1 = s, x2 = e;

        for(int d=19; d>=0; d--){
            if(t1.sps[x1][d] == 0 || t1.sps[x1][d] == t1.n) continue;
            if(t1.idx[t1.sps[x1][d]] < l) continue;
            x1 = t1.sps[x1][d];
        }
        for(int d=19; d>=0; d--){
            if(t2.sps[x2][d] == 0 || t2.sps[x2][d] == t2.n) continue;
            if(t2.idx[t2.sps[x2][d]] > r) continue;
            x2 = t2.sps[x2][d];
        }

        ans.push_back(tree.chk(1, 0, n-1, t1.l[x1], t1.r[x1], t2.l[x2], t2.r[x2]));
    }
    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 42692 KB Output is correct
2 Correct 25 ms 42652 KB Output is correct
3 Correct 24 ms 42580 KB Output is correct
4 Correct 29 ms 42584 KB Output is correct
5 Correct 24 ms 42604 KB Output is correct
6 Correct 24 ms 42700 KB Output is correct
7 Correct 24 ms 42724 KB Output is correct
8 Correct 24 ms 42628 KB Output is correct
9 Correct 31 ms 42700 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 42692 KB Output is correct
2 Correct 25 ms 42652 KB Output is correct
3 Correct 24 ms 42580 KB Output is correct
4 Correct 29 ms 42584 KB Output is correct
5 Correct 24 ms 42604 KB Output is correct
6 Correct 24 ms 42700 KB Output is correct
7 Correct 24 ms 42724 KB Output is correct
8 Correct 24 ms 42628 KB Output is correct
9 Correct 31 ms 42700 KB Output is correct
10 Correct 36 ms 44660 KB Output is correct
11 Correct 36 ms 44656 KB Output is correct
12 Correct 36 ms 44604 KB Output is correct
13 Correct 36 ms 44656 KB Output is correct
14 Correct 37 ms 44672 KB Output is correct
15 Correct 33 ms 44740 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1054 ms 175360 KB Output is correct
2 Correct 1160 ms 178096 KB Output is correct
3 Correct 914 ms 176240 KB Output is correct
4 Correct 937 ms 183772 KB Output is correct
5 Correct 1119 ms 183792 KB Output is correct
6 Correct 1022 ms 183620 KB Output is correct
7 Correct 1146 ms 183656 KB Output is correct
8 Correct 1156 ms 186392 KB Output is correct
9 Correct 965 ms 184684 KB Output is correct
10 Correct 788 ms 183972 KB Output is correct
11 Correct 958 ms 183860 KB Output is correct
12 Correct 928 ms 183748 KB Output is correct
13 Correct 1406 ms 186728 KB Output is correct
14 Correct 1268 ms 186380 KB Output is correct
15 Correct 1773 ms 186488 KB Output is correct
16 Correct 1544 ms 186572 KB Output is correct
17 Correct 1178 ms 183776 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 42692 KB Output is correct
2 Correct 25 ms 42652 KB Output is correct
3 Correct 24 ms 42580 KB Output is correct
4 Correct 29 ms 42584 KB Output is correct
5 Correct 24 ms 42604 KB Output is correct
6 Correct 24 ms 42700 KB Output is correct
7 Correct 24 ms 42724 KB Output is correct
8 Correct 24 ms 42628 KB Output is correct
9 Correct 31 ms 42700 KB Output is correct
10 Correct 36 ms 44660 KB Output is correct
11 Correct 36 ms 44656 KB Output is correct
12 Correct 36 ms 44604 KB Output is correct
13 Correct 36 ms 44656 KB Output is correct
14 Correct 37 ms 44672 KB Output is correct
15 Correct 33 ms 44740 KB Output is correct
16 Correct 1054 ms 175360 KB Output is correct
17 Correct 1160 ms 178096 KB Output is correct
18 Correct 914 ms 176240 KB Output is correct
19 Correct 937 ms 183772 KB Output is correct
20 Correct 1119 ms 183792 KB Output is correct
21 Correct 1022 ms 183620 KB Output is correct
22 Correct 1146 ms 183656 KB Output is correct
23 Correct 1156 ms 186392 KB Output is correct
24 Correct 965 ms 184684 KB Output is correct
25 Correct 788 ms 183972 KB Output is correct
26 Correct 958 ms 183860 KB Output is correct
27 Correct 928 ms 183748 KB Output is correct
28 Correct 1406 ms 186728 KB Output is correct
29 Correct 1268 ms 186380 KB Output is correct
30 Correct 1773 ms 186488 KB Output is correct
31 Correct 1544 ms 186572 KB Output is correct
32 Correct 1178 ms 183776 KB Output is correct
33 Correct 1558 ms 184636 KB Output is correct
34 Correct 360 ms 75332 KB Output is correct
35 Correct 1609 ms 186968 KB Output is correct
36 Correct 1407 ms 184344 KB Output is correct
37 Correct 1425 ms 186204 KB Output is correct
38 Correct 1435 ms 184672 KB Output is correct
39 Correct 1229 ms 189544 KB Output is correct
40 Correct 1462 ms 192496 KB Output is correct
41 Correct 1387 ms 185868 KB Output is correct
42 Correct 1114 ms 184236 KB Output is correct
43 Correct 1667 ms 190028 KB Output is correct
44 Correct 1604 ms 186160 KB Output is correct
45 Correct 904 ms 189824 KB Output is correct
46 Correct 1027 ms 189664 KB Output is correct
47 Correct 1500 ms 186764 KB Output is correct
48 Correct 1673 ms 186424 KB Output is correct
49 Correct 1335 ms 186936 KB Output is correct
50 Correct 1255 ms 186524 KB Output is correct
51 Correct 1379 ms 193140 KB Output is correct
52 Correct 1379 ms 193104 KB Output is correct