제출 #425585

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
425585		79brue	Werewolf (IOI18_werewolf)	C++14	100 / 100	1773 ms	193140 KiB

werewolf

#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 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51