Submission #1110025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110025		Mike_Vu	Werewolf (IOI18_werewolf)	C++14	100 / 100	623 ms	164680 KiB

werewolf

#ifndef mikevui
//    #include "task.h"
#endif // mikevui

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define MASK(x) (1LL<<(x))
#define BITj(x, j) (((x)>>(j))&1)

template<typename T> bool maximize(T &x, const T &y) {
    if (x < y) {x = y; return 1;}
    return 0;
}
template<typename T> bool minimize(T &x, const T &y) {
    if (x > y) {x = y; return 1;}
    return 0;
}

struct SMT{
    int trsz;
    vector<bool> tr;
    void init(int n = 0) {
        trsz = 1;
        while (trsz < n) trsz <<= 1;
        tr.assign(trsz<<1, 0);
    }
    void insval(int k, bool x) {
        tr[k+trsz-1] = x;
    }
    void build() {
        for (int i = trsz-1; i; i--) {
            tr[i] = tr[i<<1]|tr[(i<<1)|1];
        }
    }
    void update(int k, bool x) {
        k += trsz - 1;
        tr[k] = x;
        k >>= 1;
        while (k > 0) {
            tr[k] = tr[k<<1]|tr[(k<<1)|1];
            k >>= 1;
        }
    }
    bool query(int l, int r) {
        l += trsz - 1;
        r += trsz;
        bool res = 0;
        while (l < r) {
            if (l&1) res |= tr[l++];
            if (r&1) res |= tr[--r];
            l >>= 1;
            r >>= 1;
        }
        return res;
    }
    void check() {
        for (int i= 1; i <= trsz; i++) {
            cout << query(i, i) << ' ';
        }
        cout << "\n";
    }
};

struct query{
    int s, l, id;
    query(int _s, int _l, int _id){
        s = _s;
        l = _l;
        id = _id;
    }
};

const int maxn = 4e5+5, lg = 19;
int n, m, q;
vector<int> adj[maxn], ans, a[maxn];
vector<query> qu[maxn];
int tin2[maxn], tout2[maxn], h2[maxn], par2[maxn][lg+1], timer;
int pos[maxn], tin1[maxn], tout1[maxn], h1[maxn], par1[maxn][lg+1];
int sz[maxn], heavy[maxn];
SMT tr;

namespace dsu{
    vector<int> dsu;
    vector<bool> curon;
    void init() {
        dsu.assign(n+1, 0);
        curon.assign(n+1, 0);
        for (int i = 1; i <= n; i++) {
            dsu[i] = i;
            adj[i].clear();
        }
    }
    int f(int u) {
        if (u == dsu[u]) return u;
        return dsu[u] = f(dsu[u]);
    }
    void addnode(int u) {
        curon[u] = 1;
        vector<int> roots;
        for (int v : a[u]) {
            if (curon[v]) {
                roots.pb(f(v));
            }
        }
        //the same like dsu tree on edges
        sort(roots.begin(), roots.end());
        roots.erase(unique(roots.begin(), roots.end()), roots.end());
        for (int v : roots){
            dsu[v] = u;
            adj[u].pb(v);
        }
    }
}

void dfs2(int u) {
    tin2[u] = ++timer;
    //binlift
    for (int j = 1; j <= lg; j++) {
        par2[u][j] = par2[par2[u][j-1]][j-1];
    }
    for (int v : adj[u]) {
        h2[v] = h2[u]+1;
        par2[v][0] = u;
//        cout << u << ' ' << v << "\n";
        dfs2(v);
    }
    tout2[u] = timer;
}

void dfs1(int u){
    sz[u] = 1;
    tin1[u] = ++timer;
    pos[timer] = u;
    //binlift
    for (int j = 1; j <= lg; j++) {
        par1[u][j] = par1[par1[u][j-1]][j-1];
    }
    for (int v : adj[u]) {
        h1[v] = h1[u]+1;
        par1[v][0] = u;
        dfs1(v);
        sz[u] += sz[v];
    }
    tout1[u] = timer;
}

int binlift(int u, int bound, bool updo, int par[][lg+1], int h[]) {
    //updo = 0 -> (1)
    for (int j = lg; j >= 0; j--) {
        while (MASK(j) < h[u] &&
               ((updo && par[u][j] >= bound) || (!updo && par[u][j] <= bound)))
                u = par[u][j];
    }
    return u;
}

void dfssolve(int u, bool del = 0) {
    //sack on (1) -> update 2
    for (int v : adj[u]) {
        if (heavy[u] == -1 || sz[v] > sz[heavy[u]]) {
            heavy[u] = v;
        }
    }
    for (int v : adj[u]) {
        if (v == heavy[u]) continue;
        dfssolve(v, 1);
    }
    if (heavy[u] != -1) {
        dfssolve(heavy[u], 0);
    }
    //add u and light subtrees
    for (int v : adj[u]) {
        if (v == heavy[u]) continue;
        for (int x = tin1[v]; x <= tout1[v]; x++) {
            tr.update(tin2[pos[x]], 1);
        }
    }
    tr.update(tin2[u], 1);
//    cout << u << "\n";
//    tr.check();
    //solve queries at the same time -> query on (2)
    for (int i = 0; i < (int)qu[u].size(); i++) {
        int s = qu[u][i].s, l = qu[u][i].l, id = qu[u][i].id;
        int node = binlift(s, l, 1, par2, h2);
//        cout << s << ' ' << l << ' ' << id << ' ' << node << "\n";
        ans[id] = tr.query(tin2[node], tout2[node]);
    }
    //del
    if (del) {
        for (int x = tin1[u]; x <= tout1[u]; x++) {
            tr.update(tin2[pos[x]], 0);
        }
    }
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    //normalize
    n = N; m = X.size(); q = E.size();
    for (int i = 0; i < m; i++) {
        int u = X[i]+1, v = Y[i]+1;
        a[u].pb(v);
        a[v].pb(u);
    }
    //build dsu tree prefix (1), dsu tree suffix (2)
    //(2) -> segment tree
    dsu::init();
    for (int i = n; i; i--) {
        dsu::addnode(i);
    }
    //binlift
    timer = 0;
    h2[1] = 1;
    memset(par2, 0, sizeof(par2));
    dfs2(1);
    //(1)
    dsu::init();
    for (int i = 1; i <= n; i++) {
        dsu::addnode(i);
    }
    timer = 0;
    h1[n] = 1;
    memset(par1, 0, sizeof(par1));
    dfs1(n);
    //push queries
    for (int i = 0; i < q; i++) {
        int s = S[i]+1, t = E[i]+1, l = L[i]+1, r = R[i]+1;
        int u = binlift(t, r, 0, par1, h1);
//        cout << t << ' ' << r << ' ' << u << "\n";
        qu[u].pb(query(s, l, i));
    }
    //S -> (2), T -> (1)
    //root: (1) -> n, (2) -> 1
    tr.init(n);
    memset(heavy, -1, sizeof(heavy));
    ans.assign(q, 0);
    dfssolve(n);
    return ans;
}

#ifdef mikevui
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    #define name "task"
//    if (fopen(name".inp", "r")) {
//        freopen(name".inp", "r", stdin);
//        freopen(name".out", "w", stdout);
//    }
    int N, M, Q;
    vector<int> X, Y, S, E, L, R;
    cin >> N >> M >> Q;
    for (int i= 0; i < M; i++) {
        int x, y;
        cin >> x >> y;
        X.pb(x);
        Y.pb(y);
    }
    for (int i= 0; i < Q; i++) {
        int s, e, l, r;
        cin >> s >> e >> l >> r;
        S.pb(s);
        E.pb(e);
        L.pb(l);
        R.pb(r);
    }
    vector<int> res = check_validity(N, X, Y, S, E, L, R);
    for (int x : res) {
        cout << x << ' ';
    }
}
#endif // mikevui
/*
2 1 1
0 1
1 0 1 1

2 1 5
0 1
1 0 1 1
1 0 0 0
1 0 0 1
0 1 0 1
1 0 1 1

6 6 1
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2

6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/

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