Submission #851006

#	Time	Username	Problem	Language	Result	Execution time	Memory
851006		nonono	늑대인간 (IOI18_werewolf)	C++17	0 / 100	486 ms	92108 KiB

werewolf

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

const int mxN = 2e5 + 10;

struct DSU {
    vector<int> par;
    
    void init(int n) {
        par.resize(n);
        for(int i = 0; i < n; i ++) par[i] = i; 
    }
    
    int get_root(int u) {
        return par[u] == u ? u : par[u] = get_root(par[u]);
    }
};

struct TGraph { 
    int root = 0;
    vector<vector<int>> adj;    
    
    int timer = -1;
    vector<int> in, out;
    int up[mxN][20];
    DSU lnk;
    
    void init(int n) {
        adj.resize(n);    
        in.resize(n);
        out.resize(n);
        lnk.init(n);
    }
    
    void addEdge(int u, int v) {
        u = lnk.get_root(u);
        v = lnk.get_root(v);
        
        if(u == v) return ;
        
        adj[u].push_back(v); 
        lnk.par[v] = u;
        root = u;
    }
    
    void dfs(int u) {
        in[u] = ++ timer;
        
        for(int v : adj[u]) {
            up[v][0] = u;
            dfs(v);
        }
        
        out[u] = timer;
    }
    
    void build(int n) {
        up[root][0] = root;
        dfs(root);
        
        for(int k = 1; k <= 18; k ++) {
            for(int u = 0; u <= n - 1; u ++) {
                  up[u][k] = up[up[u][k - 1]][k - 1];
            }
        }
    }
    
    int get(int type, int u, int lim) {
        if(type == 0) for(int k = 18; k >= 0; k --) if(up[u][k] >= lim) u = up[u][k];
        if(type == 1) for(int k = 18; k >= 0; k --) if(up[u][k] <= lim) u = up[u][k];
        return u; 
    }
};

vector<int> fen;

void update(int i, int x, int N) {
    i ++ ;
    for(; i <= N; i += i & (- i)) fen[i] += x;
}

int get(int i) {
    int res = 0;
    i ++ ;
    for(; i > 0; i -= i & (- i)) res += fen[i];
    return res;
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {
    int Q = S.size();
    int M = X.size();
      
    vector<int> A(Q);
    vector<vector<int>> g(N);
    vector<vector<pair<int, int>>> k(N);
    vector<int> id(N);
  	TGraph tr[2];
    
    fen.resize(N + 1, 0);
    
    for (int i = 0; i < Q; ++i) {
        A[i] = 0;
    }
    
    for(int i = 0; i < M; i ++) {
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }
    
    tr[0].init(N); 
    tr[1].init(N);
    
    for(int i = N - 1; i >= 0; i --) for(int j : g[i]) if(i < j) tr[0].addEdge(i, j);
    for(int i = 0; i <= N - 1; i ++) for(int j : g[i]) if(i > j) tr[1].addEdge(i, j);
    
    tr[0].build(N); 
    tr[1].build(N);
    
    for(int i = 0; i <= Q - 1; i ++) {
        int u = tr[0].get(0, S[i], L[i]);
        E[i] = tr[1].get(1, E[i], R[i]);
        
        k[tr[0].out[u]].push_back({i, 1});
        if(tr[0].in[u]) k[tr[0].in[u] - 1].push_back({i, -1});
    }
  
    for(int i = 0; i <= N - 1; i ++) id[tr[0].in[i]] = i;
    
    for(int i = 0; i <= N - 1; i ++) {
        int x = id[i];
        update(tr[1].in[x], 1, N);
        for(auto [j, base] : k[i]) A[j] += base * (get(tr[1].out[E[j]]) - get(tr[1].in[E[j]]) - 1);
    }
    
    for(int i = 0; i <= Q - 1; i ++) A[i] = A[i] > 0;
    return A;
}

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