Submission #609589

#	Time	Username	Problem	Language	Result	Execution time	Memory
609589		skittles1412	Werewolf (IOI18_werewolf)	C++17	100 / 100	766 ms	119592 KiB

werewolf

#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__);
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

using vi = vector<int>;

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

template <typename T>
ostream& operator<<(ostream& out, const vector<T>& arr) {
    for (int i = 0; i < sz(arr); i++) {
        if (i) {
            out << " ";
        }
        out << arr[i];
    }
    return out;
}

struct ST {
    int n;
    vector<int> v;

    ST(int n) : n(n), v(4 * n, 1e9) {}

    void update(int o, int l, int r, int ind, int x) {
        if (l == r) {
            v[o] = x;
            return;
        }
        int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
        if (ind <= mid) {
            update(lc, l, mid, ind, x);
        } else {
            update(rc, mid + 1, r, ind, x);
        }
        v[o] = min(v[lc], v[rc]);
    }

    void update(int ind, int x) {
        update(1, 0, n - 1, ind, x);
    }

    int query(int o, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) {
            return v[o];
        }
        int mid = (l + r) / 2, lc = o * 2, rc = lc + 1, ans = 1e9;
        if (ql <= mid) {
            ans = min(ans, query(lc, l, mid, ql, qr));
        }
        if (mid < qr) {
            ans = min(ans, query(rc, mid + 1, r, ql, qr));
        }
        return ans;
    }

    int query(int l, int r) {
        return query(1, 0, n - 1, l, r);
    }
};

struct DSU {
    vector<int> p, pc;

    DSU(int n) : p(n, -1), pc(n, - 1) {}

    int find(int u) {
        return pc[u] < 0 ? u : (pc[u] = find(pc[u]));
    }

    void merge(int u, int v) {
        u = find(u);
        v = find(v);
        if (u != v) {
            p[u] = pc[u] = v;
        }
    }
};

struct Tree {
    int n;
    vector<int> ord;
    vector<pair<int, int>> ranges;
    vector<vector<int>> lift, graph;

    Tree(const vector<int>& p)
        : n(sz(p)), ranges(n), lift(__lg(n) + 2, vector<int>(n)), graph(n) {
        vector<int> roots;
        for (int i = 0; i < n; i++) {
            if (p[i] >= 0) {
                graph[p[i]].push_back(i);
            } else {
                roots.push_back(i);
            }
        }
        for (auto& a : roots) {
            dfs(a);
        }
        lift[0] = p;
        for (int i = 0; i <= __lg(n); i++) {
            for (int j = 0; j < n; j++) {
                if (lift[i][j] == -1) {
                    lift[i + 1][j] = -1;
                } else {
                    lift[i + 1][j] = lift[i][lift[i][j]];
                }
            }
        }
    }

    void dfs(int u) {
        ranges[u].first = sz(ord);
        ord.push_back(u);
        for (auto& v : graph[u]) {
            dfs(v);
        }
        ranges[u].second = sz(ord);
    }

    template <typename T>
    pair<int, int> bsearch(int u, const T& t) {
        for (int i = __lg(n); i >= 0; i--) {
            int v = lift[i][u];
            if (v != -1 && t(v)) {
                u = v;
            }
        }
        return ranges[u];
    }
};

vector<int> solve(const vector<int>& arr1,
                  const vector<int>& arr2,
                  const vector<array<int, 4>>& queries) {
    int n = sz(arr1), q = sz(queries);
    pair<int, int> arr[n];
    for (int i = 0; i < n; i++) {
        arr[arr1[i]].first = i;
        arr[arr2[i]].second = i;
    }
    vector<int> upds[n], qs[n];
    for (auto& [x, y] : arr) {
        upds[x].push_back(y);
    }
    for (int qi = 0; qi < q; qi++) {
        auto& [l1, r1, l2, r2] = queries[qi];
        qs[l1].push_back(qi);
    }
    bool ans[q];
    ST st(n);
    for (int i = n - 1; i >= 0; i--) {
        for (auto& a : upds[i]) {
            st.update(a, i);
        }
        for (auto& a : qs[i]) {
            auto& [l1, r1, l2, r2] = queries[a];
            ans[a] = st.query(l2, r2 - 1) < r1;
        }
    }
    return vector<int>(ans, ans + q);
}

vi check_validity(int n, vi us, vi vs, vi qsrc, vi qdest, vi ql, vi qr) {
    int q = sz(qsrc);
    vector<int> graph[n];
    for (int i = 0; i < sz(us); i++) {
        graph[us[i]].push_back(vs[i]);
        graph[vs[i]].push_back(us[i]);
    }
    DSU inc(n), dec(n);
    for (int i = 0; i < n; i++) {
        for (auto& a : graph[i]) {
            if (a <= i) {
                inc.merge(a, i);
            }
        }
    }
    for (int i = n - 1; i >= 0; i--) {
        for (auto& a : graph[i]) {
            if (a >= i) {
                dec.merge(a, i);
            }
        }
    }
    Tree inct(inc.p), dect(dec.p);
    vector<array<int, 4>> queries(q);
    for (int qi = 0; qi < q; qi++) {
        int src = qsrc[qi], dest = qdest[qi], l = ql[qi], r = qr[qi];
        auto [il, ir] = inct.bsearch(dest, [&](int x) -> bool {
            return x <= r;
        });
        auto [dl, dr] = dect.bsearch(src, [&](int x) -> bool {
            return x >= l;
        });
        queries[qi] = {il, ir, dl, dr};
    }
    dbg("A");
    return solve(inct.ord, dect.ord, queries);
}

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