Submission #98884

#	Time	Username	Problem	Language	Result	Execution time	Memory
98884		dlalswp25	Werewolf (IOI18_werewolf)	C++14	34 / 100	2525 ms	100292 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> adj[202020];
vector<int> tre[202020];
int Q, M, N;

int p[202020];
int st[20][202020];
int mn[20][202020];
int mx[20][202020];
int dep[202020];

int fd(int x) {
    if(x == p[x]) return x;
    return p[x] = fd(p[x]);
}
void unite(int a, int b) {
    a = fd(a); b = fd(b);
    if(a == b) return;
    p[a] = b;
}

void dfs(int now, int par) {
    dep[now] = dep[par] + 1;
    
    st[0][now] = mx[0][now] = mn[0][now] = par;
    if(!now) mn[0][now] = -1;
    
    for(int i : tre[now]) {
        if(i == par) continue;
        dfs(i, now);
    }
}

int lca(int a, int b) {
    if(dep[a] < dep[b]) return lca(b, a);
    for(int i = 19; i >= 0; i--) {
        if(dep[st[i][a]] < dep[b]) continue;
        a = st[i][a];
    }
    if(a == b) return a;
    for(int i = 19; i >= 0; i--) {
        if(st[i][a] == st[i][b]) continue;
        a = st[i][a]; b = st[i][b];
    }
    return st[0][a];
}

int find_yellow(int v, int u, int x) {
    if(v > x) return v;
    for(int i = 19; i >= 0; i--) {
        if(mx[i][v] > x) continue;
        if(dep[st[i][v]] < dep[u]) continue;
        v = st[i][v];
    }
    return v;
}

int find_blue(int v, int u, int x) {
    if(v < x) return v;
    for(int i = 19; i >= 0; i--) {
        if(mn[i][v] < x) continue;
        if(dep[st[i][v]] < dep[u]) continue;
        v = st[i][v];
    }
    return v;
}

vector<int> ans;

void yes() { ans.push_back(1); }
void no() { ans.push_back(0); }

std::vector<int> check_validity(int _N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
    Q = S.size();
    M = X.size();
    N = _N;
    
    for(int i = 0; i < M; i++) {
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }
    
    for(int i = 0; i < N; i++) sort(adj[i].begin(), adj[i].end());
    for(int i = 0; i < N; i++) p[i] = i;
    
    for(int i = N - 2; i >= 0; i--) {
        for(int j : adj[i]) {
            if(fd(j) == fd(i)) continue;
            tre[i].push_back(j);
            tre[j].push_back(i);
            unite(i, j);
        }
    }
    
    dfs(0, 200002);
    
    for(int i = 1; i <= 19; i++) {
        for(int j = 0; j < N; j++) {
            st[i][j] = st[i - 1][st[i - 1][j]];
            mn[i][j] = min(mn[i - 1][j], mn[i - 1][st[i - 1][j]]);
            mx[i][j] = max(mx[i - 1][j], mx[i - 1][st[i - 1][j]]);
        }
    }

    for(int i = 0; i < Q; i++) {
        if(S[i] < L[i] || E[i] > R[i]) { no(); continue; }
        
        int l = lca(S[i], E[i]);
        int s = S[i], e = E[i];
        
        s = find_blue(s, l, L[i]);
        e = find_yellow(e, l, R[i]);
        
        if(s == l && e == l) {
            yes(); continue;
        }
        
        if(dep[s] > dep[l]) s = find_yellow(s, l, R[i]);
        else e = find_blue(e, l, L[i]);
        
        if(s == l && e == l) yes();
        else no();
    }
    return ans;
}

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