Submission #1201921

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201921		tfgs	Werewolf (IOI18_werewolf)	C++17	100 / 100	389 ms	104348 KiB

werewolf

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

using namespace std;
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#pragma GCC target("avx2")

#ifdef LOCAL
#include "algo/debug.h"
#else
template <typename... Args>
void dummy(Args&&... args){}
#define ps dummy
#endif

#define f first
#define s second
template<class T> using V = vector<T>; 
using vi = V<int>;
using vb = V<bool>;
using vs = V<string>;

#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x) 
#define len(x) (int)((x).size())
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pb push_back
#define eb emplace_back
#define pf push_front
#define lb lower_bound
#define ub upper_bound
#define ai2 array<int,2>
#define ai3 array<int,3>
#define ai4 array<int,4>
#define ai5 array<int,5>
template<class T> int lwb(const V<T>& a, const T& b) { return lb(all(a),b)-begin(a); }
template<class T> int upb(const V<T>& a, const T& b) { return ub(all(a),b)-begin(a); }
template<class T> bool ckmin(T& a, const T& b) { return a > b ? a=b, true : false; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a=b, true : false; }
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define clz __builtin_clzll
constexpr int p2(int x) { return (int)1 << x; }
constexpr int msk2(int x) { return (int)(1 << x) - 1; }
constexpr int bits(int x) { return x == 0 ? 0 : 63-clz(x); } // floor(log2(x)) 
template<class T>void UNIQUE(V<T>& v) { sort(all(v)); v.erase(unique(all(v)),end(v)); }
template<class T, class Cmp>void UNIQUE(V<T>& v, Cmp cmp) { sort(all(v), cmp); v.erase(unique(all(v)),end(v)); }
template<class T,class U>void erase(T& t, const U& u) { auto it = t.find(u); assert(it != end(t)); t.erase(it); }
template<class F> struct y_combinator_result {
    F f;
    template<class T> explicit y_combinator_result(T &&f): f(std::forward<T>(f)) {}
    template<class ...Args> decltype(auto) operator()(Args &&...args) { return f(std::ref(*this), std::forward<Args>(args)...); }
};
template<class Fun> decltype(auto) yy(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }

template<class T> struct Bit {
    int n;
    V<T> a;
    void point_add(int i, T x) {
        for (; i <= n; i += i & -i) {
            a[i] += x;
        }
    }
    T prefix_sum(int r) {
        T res = 0;
        for (; r > 0; r -= r & -r) {
            res += a[r];
        }
        return res;
    }
    T query(int l, int r) { return prefix_sum(r) - prefix_sum(l - 1); }
    Bit(int n) : n(n), a(n + 1) {}
};

const int LOG = 20;

struct Dsu {
    int timer;
    vector<int> par, tin, tout, order;
    vector<vector<int>> adj;

    Dsu(int n) : timer(0), par(n), tin(n), tout(n), order({n}), adj(n) {
        iota(par.begin(), par.end(), 0);
    }

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

    void unite(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v)
            return;
        par.push_back((int) par.size());
        par[u] = par[v] = (int) par.size() - 1;
        tin.emplace_back();
        tout.emplace_back();
        adj.push_back({u, v});
    }

    void dfs(int u) {
        tin[u] = ++timer;
        order.push_back(u);
        for (int v : adj[u])
            dfs(v);
        tout[u] = timer;
    }
};

#ifdef LOCAL
void solve() {
    int N, M, Q; cin >> N >> M >> Q;
    vi X(M), Y(M);
    for (int i = 0; i < M; i++) cin >> X[i] >> Y[i];
    vi S(Q), E(Q), L(Q), R(Q);
    for (int i = 0; i < Q; i++) cin >> S[i] >> E[i] >> L[i] >> R[i];
#else
vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
    int Q = len(S);
    int M = len(X);
#endif

    V<vi> g(N);
    for (int i = 0; i < M; i++) g[X[i]].pb(Y[i]), g[Y[i]].pb(X[i]);

    V<vi> query_l(N), query_r(N);
    for (int i = 0; i < Q; i++) {
        query_l[L[i]].pb(i);
        query_r[R[i]].pb(i);
    }

    Dsu inc(N), dec(N);
    for (int u = 0; u < N; u++) {
        for (int v : g[u]) if (v < u) inc.unite(u, v);
        for (int qi : query_r[u]) E[qi] = inc.find(E[qi]);
    }
    for (int u = N - 1; u >= 0; u--) {
        for (int v : g[u]) if (v > u) dec.unite(u, v);
        for (int qi : query_l[u]) S[qi] = dec.find(S[qi]);
    }

    inc.dfs(inc.find(0));
    dec.dfs(dec.find(0));

    // for each query, we want to find the number of shared values b/w
    // inc.order[inc.tin[E[qi]], inc.tout[E[qi]]] and dec.order[dec.tin[S[qi]], dec.tout[S[qi]]]
    // where S[qi] and E[qi] represent the nodes in the KRT for all >= L and <= R, respectievly.

    int o1 = inc.order.size(), o2 = dec.order.size();
    V<V<ai2>> evs(o1);
    Bit<int> bit(o2);
    for (int qi = 0; qi < Q; qi++) {
        evs[inc.tin[E[qi]] - 1].pb({ qi, -1 });
        evs[inc.tout[E[qi]]].pb({ qi, 1 });
    }

    vi ans(Q);
    for (int i = 0; i < o1; i++) {
        if (inc.order[i] < N) {
            bit.point_add(dec.tin[inc.order[i]], 1);
        }
        for (auto [qi, sign] : evs[i]) {
            ans[qi] += sign * bit.query(dec.tin[S[qi]], dec.tout[S[qi]]);
        }
    }

    // vector evs(o1, V<ai4>());
    // for (int qi = 0; qi < Q; qi++) {
        // int l_a = dec.tin[S[qi]], r_a = dec.tout[S[qi]];
        // int l_b = inc.tin[E[qi]], r_b = dec.tout[E[qi]];
        // ps(l_b, r_b, N);
        // evs[r_b].pb({ l_a, r_a, 1, qi });
        // evs[l_b].pb({ l_a, r_a, -1, qi });
    // }

    // vi ans(Q);
    // Bit<int> bit(N);
    // for (int i = 0; i <= N; i++) {
        // for (auto [l_a, r_a, sign, qi] : evs[i]) {
            // ans[qi] += sign * (bit.prefix_sum(r_a + 1) - bit.prefix_sum(l_a));
        // }

        // if (i < N) bit.point_add(inc.tin[inc.order[i]], 1);
    // }


    for (int& i : ans) i = bool(i);

#ifdef LOCAL
    for (int i : ans) cout << i << '\n';
#else
    return ans;
#endif
}

#ifdef LOCAL
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}
#endif

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