제출 #585825

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
585825		alireza_kaviani	늑대인간 (IOI18_werewolf)	C++17	0 / 100	406 ms	338568 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

#define all(x)  (x).begin(), (x).end()
#define SZ(x)   int((x).size())
#define X       first
#define Y       second
#define sep     ' '

const int LOG = 22;
const int MAXN = 5e5 + 10;

int n , m , q , curInd , Root[2] , Par[MAXN] , sz[MAXN] , root[MAXN] , value[2][MAXN] , par[2][LOG][MAXN];
int timer , st[MAXN] , fn[MAXN];
vector<pair<int, pii>> Edge[2];
vector<int> adj[2][MAXN] , ans;
vector<pii> Q[MAXN];
set<int> ST[MAXN];

int Find(int v){
    return (Par[v] == -1 ? v : Par[v] = Find(Par[v]));
}

void Union(int ind , int v , int u , int w){
    v = Find(v); u = Find(u);
    if(u == v)    return;
    if(sz[v] < sz[u])   swap(v , u);
    Par[u] = v;
    sz[v] += sz[u];
    //cout << curInd << sep << root[v] << sep << root[u] << sep << w << endl;
    par[ind][0][root[v]] = par[ind][0][root[u]] = curInd;
    adj[ind][curInd].push_back(root[v]);
    adj[ind][curInd].push_back(root[u]);
    value[ind][curInd] = w;
    root[v] = curInd++;
}

void PreDFS(int v){
    st[v] = timer++;
    for(int u : adj[0][v]){
        PreDFS(u);
    }
    fn[v] = timer;
}

void SolveDFS(int v){
    if(v < n){
        ST[v].insert(st[v]);
    }
    for(int u : adj[1][v]){
        SolveDFS(u);
        if(SZ(ST[u]) > SZ(ST[v])){
            ST[v].swap(ST[u]);
        }
        for(int j : ST[u]){
            ST[v].insert(j);
        }
    }
    for(pii i : Q[v]){
        int u = i.X , ind = i.Y;
        auto it = ST[v].lower_bound(st[u]);
        if(it != ST[v].end() && (*it) < fn[u]){
            ans[ind] = 1;
        }
    }
}

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 = SZ(X); q = SZ(S);
    for(int i = 0 ; i < m ; i++){
        int v = X[i] , u = Y[i];
        Edge[0].push_back({max(v , u) , {v , u}});
        Edge[1].push_back({min(v , u) , {v , u}});
    }
    sort(all(Edge[0]));
    sort(all(Edge[1]) , greater<pair<int , pii>>());

    for(int i = 0 ; i < 2 ; i++){
        curInd = n;
        for(int j = 0 ; j < MAXN ; j++){
            Par[j] = -1;
            sz[j] = 1;
            root[j] = j;
        }
        for(auto &j : Edge[i]){
            Union(i , j.Y.X , j.Y.Y , j.X);
        }
        par[i][0][curInd - 1] = curInd - 1;
        for(int j = 1 ; j < LOG ; j++){
            for(int k = 0 ; k < curInd ; k++){
                par[i][j][k] = par[i][j - 1][par[i][j - 1][k]];
            }
        }
        Root[i] = curInd - 1;
    }

    ans = vector<int>(q , 0);
    for(int i = 0 ; i < q ; i++){
        int v = S[i] , u = E[i] , l = L[i] , r = R[i];
        for(int j = LOG - 1 ; j >= 0 ; j--){
            if(value[0][par[0][i][u]] <= r){
                u = par[0][i][u];
            }
            if(value[1][par[1][i][v]] >= l){
                v = par[1][i][v];
            }
        }
        Q[v].push_back({u , i});
    }
    PreDFS(Root[0]);
    SolveDFS(Root[1]);

    return ans;
}

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