제출 #293316

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
293316		Atill83	늑대인간 (IOI18_werewolf)	C++14	100 / 100	1253 ms	124588 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
const int MAXN = (int) 5e5 + 5;
int n;
int t[MAXN];

void upd(int v, int val){
    for(; v < MAXN; v += (v&-v))
        t[v] += val;
}

int gt(int l, int r){
    l--;
    int res = 0;
    for(; r; r -= (r&-r)) res += t[r];
    for(; l; l -= (l&-l)) res -= t[l];
    return res;
}


vector<pair<int, int>> Qs[MAXN];
vector<int> A;
struct ali{
    int cev[MAXN], tin[MAXN], tout[MAXN], sz[MAXN], pari[MAXN][22];
    int cur = 1;
    int par[MAXN];
    vector<int> adj[MAXN];
    void ini(){
        for(int i = 0; i < n; i++){
            adj[i].clear();
            sz[i] = 1;
            par[i] = i;
            pari[i][0] = i;
        }
    }

    int find_set(int v){
        if(par[v] == v) return v;
        return par[v] = find_set(par[v]);
    }

    void merge(int a, int b, bool cr){
        a = find_set(a);
        b = find_set(b);
        if(a == b) return;
        if(cr){
            if(a < b)
                swap(a, b);

            sz[a] += sz[b];
            par[b] = a;
            pari[b][0] = a;
            adj[a].push_back(b);
        }else{
            if(a > b)
                swap(a, b);
            sz[a] += sz[b];
            par[b] = a;
            pari[b][0] = a;
            adj[a].push_back(b);
        }
    }

    void dfs(int v){
        tin[v] = cur++;
        cev[cur - 1] = v;
        for(int l = 1; l < 22; l++)
            pari[v][l] = pari[pari[v][l - 1]][l - 1];
        for(int j: adj[v])
            dfs(j);
        tout[v] = cur - 1;
    }


    void dfs2(int v, bool keep, ali &s){
        int hv = -1;
        for(int j: adj[v])
            if(hv == -1 || sz[j] > sz[hv]) 
                hv = j;

        for(int j: adj[v])
            if(j != hv) 
                dfs2(j, 0, s);

        if(hv != -1)
            dfs2(hv, 1, s);

        for(int j: adj[v])
            if(j != hv)
                for(int i = tin[j]; i <= tout[j]; i++)
                    upd(s.tin[cev[i]], 1);

        upd(s.tin[v], 1);
        for(auto j: Qs[v]){
            int rs = gt(s.tin[j.first], s.tout[j.first]);
            assert(rs >= 0);
            A[j.second] = (rs != 0);
        }

        if(keep == 0)
            for(int i = tin[v]; i <= tout[v]; i++)
                upd(s.tin[cev[i]], -1);
    }

} st1, st2;






vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
    n = N;
    int M = X.size(), Q = S.size();
    st1.ini(); 
    st2.ini();
    A.resize(Q);
    vector<int> esi;
    for(int i = 0; i < M; i++){
        esi.push_back(i);
    }

    sort(esi.begin(), esi.end(), [&X, &Y](int a, int b){
        if(min(X[a], Y[a]) == min(X[b], Y[b])){
            return max(X[a], Y[a]) < max(X[b], Y[b]);
        }
        return min(X[a], Y[a]) > min(X[b], Y[b]);
    });
    st1.ini(); st2.ini();
    for(int i = 0; i < M; i++){
        st1.merge(X[esi[i]], Y[esi[i]], 0);
    }

    sort(esi.begin(), esi.end(), [&X, &Y](int a, int b){
        if(max(X[a], Y[a]) == max(X[b], Y[b]))
            return min(X[a], Y[a]) > min(X[b], Y[b]);
        return max(X[a], Y[a]) < max(X[b], Y[b]);
    });

    for(int i = 0; i < M; i++){
        st2.merge(X[esi[i]], Y[esi[i]], 1);
    }
    st1.dfs(0);
    st2.dfs(n - 1);
    for(int i = 0; i < Q; i++){

        for(int j = 21; j >= 0; j--){
            if(st1.pari[S[i]][j] >= L[i]){
                S[i] = st1.pari[S[i]][j];
            }
        }

        for(int j = 21; j >= 0; j--){
            if(st2.pari[E[i]][j] <= R[i]){
                E[i] = st2.pari[E[i]][j];
            }
        }
        Qs[S[i]].push_back({E[i], i});
    }

    st1.dfs2(0, 1, st2);
    return A;
}

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