Submission #778392

#	Time	Username	Problem	Language	Result	Execution time	Memory
778392		IBory	Werewolf (IOI18_werewolf)	C++17	100 / 100	869 ms	187516 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int SZ = 1 << 19;
int inv[SZ];

struct BIT {
    int T[SZ];
    void Update(int i, int v) {
        for (; i < SZ; i += i & -i) T[i] += v;
    }
    int Query(int L, int R) {
        int ret = 0; L--;
        for (; R; R -= R & -R) ret += T[R];
        for (; L; L -= L & -L) ret -= T[L];
        return ret;
    }
} T;

struct UFTree {
    int R[SZ], A[SZ], in[SZ], out[SZ], P[19][SZ], node, dn;
    vector<int> G[SZ];

    UFTree(int N, vector<pii>& E, int type) {
        iota(R, R + SZ, 0);
        node = N - 1;
        Construct(E, type);
        DFS(node);
    }

    int Find(int n) {
        if (n == R[n]) return n;
        return R[n] = Find(R[n]);
    }

    bool Union(int a, int b, int c) {
        R[a] = c, R[b] = c;
        return 1;
    }

    void Construct(vector<pii>& E, int type) {
        for (int i = 0; i <= node; ++i) A[i] = i;
        for (auto [a, b] : E) {
            a = Find(a), b = Find(b);
            if (a != b) {
                P[0][a] = P[0][b] = ++node;
                Union(a, b, node);
                G[node].push_back(a);
                G[node].push_back(b);
                A[node] = (type == 1 ? max(A[a], A[b]) : min(A[a], A[b]));
            }
        }

        P[0][node] = node;
        for (int n = 1; n < 19; ++n) for (int i = 0; i <= node; ++i) {
            P[n][i] = P[n - 1][P[n - 1][i]];
        }
    }

    void DFS(int cur) {
        in[cur] = ++dn;
        for (int next : G[cur]) DFS(next);
        out[cur] = dn;
    }
};

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(), Q = S.size();
    vector<pii> Eord[2];
    for (int i = 0; i < M; ++i) {
        Eord[0].emplace_back(X[i], Y[i]);
        Eord[1].emplace_back(X[i], Y[i]);
    }

    sort(Eord[0].begin(), Eord[0].end(), [&](pii& a, pii& b) {
        return max(a.first, a.second) < max(b.first, b.second);
    });
    sort(Eord[1].begin(), Eord[1].end(), [&](pii& a, pii& b) {
        return min(a.first, a.second) > min(b.first, b.second);
    });

    UFTree T1(N, Eord[1], 0);
    UFTree T2(N, Eord[0], 1);
    vector<int> ans(Q);
    vector<pair<pii, pair<pii, int>>> Qord;
    for (int i = 0; i < Q; ++i) {
        int s = S[i], e = E[i];
        for (int n = 18; n >= 0; --n) {
            if (L[i] <= T1.A[T1.P[n][s]]) s = T1.P[n][s];
            if (T2.A[T2.P[n][e]] <= R[i]) {
                e = T2.P[n][e];
            }
        }
        pii r = {T2.in[e], T2.out[e]};
        Qord.emplace_back(pii{T1.in[s], -1}, pair<pii, int>{r, i});
        Qord.emplace_back(pii{T1.out[s], 1}, pair<pii, int>{r, i});
    }
    pii dummy = {0, 0};
    for (int i = 0; i < N; ++i) Qord.emplace_back(pii{T1.in[i], 0}, pair<pii, int>{dummy, Q});

    sort(Qord.begin(), Qord.end());
    for (int i = 0; i < N; ++i) inv[T1.in[i]] = T2.in[i];
    for (auto [p1, p2] : Qord) {
        auto [x, type] = p1;
        auto [p3, qn] = p2;
        auto [l, r] = p3;
        if (type == -1) ans[qn] -= T.Query(l, r);
        else if (type == 0) T.Update(inv[x], 1);
        else ans[qn] += T.Query(l, r);
    }
    
    for (int& n : ans) n = n > 0;
    return ans;
}

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