oj.uz

Submission #425581

# Submission time Handle Problem Language Result Execution time Memory
425581 2021-06-13T07:55:10 Z 79brue Werewolf (IOI18_werewolf) C++14
0 / 100
 1391 ms 184804 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(){
        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) 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) 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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 42720 KB Output is correct
2 Correct 28 ms 42660 KB Output is correct
3 Correct 28 ms 42668 KB Output is correct
4 Incorrect 31 ms 42636 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 42720 KB Output is correct
2 Correct 28 ms 42660 KB Output is correct
3 Correct 28 ms 42668 KB Output is correct
4 Incorrect 31 ms 42636 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1391 ms 175348 KB Output is correct
2 Correct 1284 ms 178076 KB Output is correct
3 Incorrect 1108 ms 184804 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 42720 KB Output is correct
2 Correct 28 ms 42660 KB Output is correct
3 Correct 28 ms 42668 KB Output is correct
4 Incorrect 31 ms 42636 KB Output isn't correct
5 Halted 0 ms 0 KB -