Submission #413593

#	Time	Username	Problem	Language	Result	Execution time	Memory
413593		timmyfeng	Werewolf (IOI18_werewolf)	C++17	100 / 100	912 ms	114480 KiB

werewolf

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

const int N = 200000, L = __lg(N) + 1;

struct segtree {
    segtree *left, *right;
    int maxi;

    segtree(int l, int r) {
        maxi = 0;
        if (l < r) {
            int m = (l + r) / 2;
            left = new segtree(l, m);
            right = new segtree(m + 1, r);
        }
    }

    void update(int a, int x, int l, int r) {
        if (l == r) {
            maxi = x;
        } else {
            int m = (l + r) / 2;
            if (a <= m) {
                left->update(a, x, l, m);
            } else {
                right->update(a, x, m + 1, r);
            }
            maxi = max(left->maxi, right->maxi);
        }
    }

    int query(int a, int b, int l, int r) {
        if (b < l || r < a) {
            return INT_MIN;
        } else if (a <= l && r <= b) {
            return maxi;
        } else {
            int m = (l + r) / 2;
            return max(
                left->query(a, b, l, m),
                right->query(a, b, m + 1, r)
            );
        }
    }
};

int in_l[N], out_l[N], par_l[L][N], in_r[N], out_r[N], par_r[L][N], t;
vector<int> tree_l[N], tree_r[N];

int dsu[N];

int find(int u) {
    if (dsu[u] == -1) {
        return u;
    }
    dsu[u] = find(dsu[u]);
    return dsu[u];
}

void dfs(int u, vector<int> *adj, int *in, int *out, int *par) {
    in[u] = ++t;
    for (auto c : adj[u]) {
        par[c] = u;
        dfs(c, adj, in, out, par);
    }
    out[u] = t;
}

vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r) {
    int m = x.size();
    vector<vector<int>> adj(n);
    for (int i = 0; i < m; ++i) {
        adj[x[i]].push_back(y[i]);
        adj[y[i]].push_back(x[i]);
    }

    fill(dsu, dsu + n, -1);
    for (int i = 0; i < n; ++i) {
        for (auto j : adj[i]) {
            if (j < i && find(j) != i) {
                tree_l[i].push_back(find(j));
                dsu[find(j)] = i;
            }
        }
    }
    par_l[0][n - 1] = n - 1;
    dfs(n - 1, tree_l, in_l, out_l, par_l[0]);

    fill(dsu, dsu + n, -1);
    for (int i = n - 1; i >= 0; --i) {
        for (auto j : adj[i]) {
            if (j > i && find(j) != i) {
                tree_r[i].push_back(find(j));
                dsu[find(j)] = i;
            }
        }
    }
    par_r[0][0] = 0;
    dfs(0, tree_r, in_r, out_r, par_r[0]);

    for (int i = 1; i <= __lg(n); ++i) {
        for (int j = 0; j < n; ++j) {
            par_l[i][j] = par_l[i - 1][par_l[i - 1][j]];
            par_r[i][j] = par_r[i - 1][par_r[i - 1][j]];
        }
    }

    int q = s.size();
    vector<array<int, 3>> queries;
    for (int i = 0; i < q; ++i) {
        for (int j = __lg(n); j >= 0; --j) {
            if (par_l[j][e[i]] <= r[i]) {
                e[i] = par_l[j][e[i]];
            }

            if (par_r[j][s[i]] >= l[i]) {
                s[i] = par_r[j][s[i]];
            }
        }
        queries.push_back({out_r[s[i]], 1, i});
    }

    for (int i = 0; i < n; ++i) {
        queries.push_back({in_r[i], 0, in_l[i]});
    }
    sort(queries.begin(), queries.end());

    vector<int> ans(q);
    segtree *maxi = new segtree(1, n);
    for (auto [a, b, c] : queries) {
        if (b == 0) {
            maxi->update(c, a, 1, n);
        } else {
            ans[c] = maxi->query(in_l[e[c]], out_l[e[c]], 1, n) >= in_r[s[c]];
        }
    }

    return ans;
}

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