Submission #588670

#	Time	Username	Problem	Language	Result	Execution time	Memory
588670		georgievskiy	Werewolf (IOI18_werewolf)	C++17	100 / 100	1148 ms	123100 KiB

werewolf

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

struct DSU {
    vector<vector<int>> g;
    vector<int> link;
    vector<int> euler, l, r;

    DSU(int n) {
        g.resize(n), link.resize(n);
        l.resize(n), r.resize(n);
        iota(link.begin(), link.end(), 0);
    }

    int getP(int x) {
        if (link[x] == x) return x;
        return link[x] = getP(link[x]);
    }

    void unite(int dad, int son) {
        dad = getP(dad), son = getP(son);
        if (dad == son) return;
        link[son] = dad;
        g[dad].push_back(son);
    }

    void dfs(int v) {
        l[v] = euler.size();
        euler.push_back(v);
        for (int u : g[v])
            dfs(u);
        r[v] = euler.size();
    }
};

struct MST {
    vector<vector<int>> t;
    MST(vector<int>& a) {
        t.resize(a.size() * 4);
        build(0, 0, a.size(), a);
    }
    void build(int v, int tl, int tr, vector<int>& a) {
        if (tl + 1 == tr) {
            t[v].push_back(a[tl]);
            return;
        }
        int m = (tl + tr) / 2;
        build(2 * v + 1, tl, m, a);
        build(2 * v + 2, m, tr, a);
        t[v].resize(t[2 * v + 1].size() + t[2 * v + 2].size());
        merge(t[2 * v + 1].begin(), t[2 * v + 1].end(), t[2 * v + 2].begin(), t[2 * v + 2].end(), t[v].begin());
    }

    int get(int v, int tl, int tr, int l, int r, int lo, int hi) {
        if (tl >= r || tr <= l)
            return 0;
        if (tl >= l && tr <= r) {
            return lower_bound(t[v].begin(), t[v].end(), hi) - lower_bound(t[v].begin(), t[v].end(), lo);
        }
        int m = (tl + tr) / 2;
        return get(2 * v + 1, tl, m, l, r, lo, hi) + get(2 * v + 2, m, tr, l, r, lo, hi);
    }
};

std::vector<int> check_validity(int n, std::vector<int> X, std::vector<int> Y,
        std::vector<int> S, std::vector<int> E,std::vector<int> L, std::vector<int> R) {
    int m = X.size(), q = S.size();
    vector<vector<int>> g(n);
    for (int i = 0; i < m; i++)
        g[X[i]].push_back(Y[i]), g[Y[i]].push_back(X[i]);
    vector<vector<int>> le(n), re(n);
    for (int i = 0; i < q; i++)
        le[L[i]].push_back(i), re[R[i]].push_back(i);

    vector<int> lp(q);
    DSU dl(n);
    for (int i = n - 1; i >= 0; i--) {
        for (int j : g[i])
            if (j > i)
                dl.unite(i, j);
        for (int ind : le[i])
            lp[ind] = dl.getP(S[ind]);
    }
    int dl_root = dl.getP(0);
    dl.dfs(dl_root);

    vector<int> rp(q);
    DSU dr(n);
    for (int i = 0; i < n; i++) {
        for (int j : g[i])
            if (j < i)
                dr.unite(i, j);
        for (int ind : re[i])
            rp[ind] = dr.getP(E[ind]);
    }
    int dr_root = dr.getP(0);
    dr.dfs(dr_root);

    vector<int> p_dl(n);
    for (int i = 0; i < n; i++)
        p_dl[dl.euler[i]] = i;

    vector<int> a(n);
    for (int i = 0; i < n; i++)
        a[i] = p_dl[dr.euler[i]];

    vector<int> ans(q);
    MST t(a);
    for (int i = 0; i < q; i++) {
        int l1 = dl.l[lp[i]], r1 = dl.r[lp[i]];
        int l2 = dr.l[rp[i]], r2 = dr.r[rp[i]];
        int x = t.get(0, 0, n, l2, r2, l1, r1);
        ans[i] = x > 0;
    }

    return ans;
}

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