Submission #116150

#	Time	Username	Problem	Language	Result	Execution time	Memory
116150		RezwanArefin01	Werewolf (IOI18_werewolf)	C++17	100 / 100	1732 ms	169324 KiB

werewolf

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

typedef vector<int> vi; 
typedef vector<vi> vvi; 

const int N = 2e5 + 10; 
vi adj[N], t[N << 2];  
int n, p[N], idx, vert[N];

void build(int node, int l, int r, vi &in) {
    if(l == r) {
        t[node].push_back(in[vert[l]]); 
        return; 
    }
    int m = l + r >> 1; 
    build(node << 1, l, m, in); 
    build(node << 1 | 1, m + 1, r, in); 

    merge(t[node << 1].begin(), t[node << 1].end(), 
        t[node << 1 | 1].begin(), t[node << 1 | 1].end(), 
        back_inserter(t[node]));
}

bool query(int node, int l, int r, int i, int j, int x, int y) {
    if(r < i || l > j) return 0; 
    if(i <= l && r <= j) {
        vi &v = t[node];
        auto L = lower_bound(v.begin(), v.end(), x); 
        if(L == v.end()) return 0; 
        return *L <= y; 
    }
    int m = l + r >> 1; 
    return query(node << 1, l, m, i, j, x, y) || 
        query(node << 1 | 1, m + 1, r, i, j, x, y); 
}

int find(int u) {
    return u == p[u] ? u : p[u] = find(p[u]); 
}

void build_rt(bool wolf, vector<vi> &t) {
    int st = wolf ? 0 : n - 1; 
    int ed = wolf ? n : -1; 
    int inc = wolf ? 1 : -1; 

    iota(p, p + N, 0); 

    for(int i = st; i != ed; i += inc) {
        for(int v : adj[i]) {
            if((wolf && v > i) || (!wolf && v < i)) break; 
            v = find(v);
            if(v == i) continue;
            p[v] = i;
            t[i].push_back(v);
        }
    }
}

void dfs(vvi &t, vvi &p, vi &in, vi &out, int u, int par, bool wolf = 0) {
    in[u] = ++idx;
    if(wolf) vert[idx] = u;
    p[u][0] = par; 
    for(int i = 1; i <= 18; ++i) if(p[u][i - 1] + 1) 
        p[u][i] = p[p[u][i - 1]][i - 1]; 
    for(int v : t[u]) if(v - par) 
        dfs(t, p, in, out, v, u, wolf); 
    out[u] = idx;
}

int walk(vvi &p, int u, int k, bool wolf) {
    for(int i = 18; i >= 0; --i) if(p[u][i] + 1) {
        int v = p[u][i];
        if((wolf && v <= k) || (!wolf && v >= k)) {
            u = v;
        }
    }
    return u;
}

vi check_validity(int _N, vi X, vi Y, vi S, vi E, vi L, vi R) {
    n = _N;
    for(int i = 0; i < X.size(); ++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()); 

    vvi pw(n, vi(19, -1)); 
    vvi ph(n, vi(19, -1)); 
    vvi tw(n), th(n);
    vi iw(n), ow(n), ih(n), oh(n); 

    build_rt(1, tw); 
    for(int i = 0; i < n; ++i) 
        reverse(adj[i].begin(), adj[i].end()); 
    build_rt(0, th);


    dfs(tw, pw, iw, ow, n - 1, -1, 1); 
    idx = 0; 
    dfs(th, ph, ih, oh, 0, -1); 

    build(1, 1, n, ih); 

    int Q = S.size();
    vi ans(Q);  

    for(int i = 0; i < Q; ++i) {
        int u = walk(ph, S[i], L[i], 0);
        int v = walk(pw, E[i], R[i], 1); 

        ans[i] = query(1, 1, n, iw[v], ow[v], ih[u], oh[u]);
    }

    return ans;
}

Compilation message (stderr)

werewolf.cpp: In function 'void build(int, int, int, vi&)':
werewolf.cpp:17:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = l + r >> 1; 
             ~~^~~
werewolf.cpp: In function 'bool query(int, int, int, int, int, int, int)':
werewolf.cpp:34:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = l + r >> 1; 
             ~~^~~
werewolf.cpp: In function 'vi check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:84:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < X.size(); ++i) {
                    ~~^~~~~~~~~~

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