Submission #1125248

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125248		Pekiban	Werewolf (IOI18_werewolf)	C++20	100 / 100	3844 ms	140560 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;
#define pb push_back

const int N = 4e5 + 5, LOG = 19, SQ = 600;
struct krt {
    vector<int> g[N];
    int a[N], p[N], W[N], tin[N], tout[N], up[LOG][N], C, tm;
    bool fl = 0; // fl = 1 za MX, 0 za MN
    void init(int n) {
        C = n-1;
        iota(p, p+N, 0);
        iota(W, W+N, 0);
    }
    int get(int x) {
        if (x == p[x])  return x;
        return p[x] = get(p[x]);
    }
    bool unite(int u, int v) {
        u = get(u), v = get(v);
        if (u == v) return 0;
        p[u] = p[v] = ++C;
        W[C] = (fl ? min(W[u], W[v]) : max(W[u], W[v]));
        g[C].pb(u); g[C].pb(v); g[u].pb(C); g[v].pb(C);
        return 1;
    }
    void dfs(int s, int e = -1) {
        tin[s] = ++tm;
        a[tm] = s;
        for (auto u : g[s]) {
            if (u == e) continue;
            up[0][u] = s;
            dfs(u, s);
        }
        tout[s] = tm;
    }
    void init2() {
        dfs(C);
        up[0][C] = C+1;
        up[0][C+1] = C+1;
        for (int i = 1; i < LOG; ++i) {
            for (int j = 0; j <= C+1; ++j)    up[i][j] = up[i-1][up[i-1][j]];
        }
    }
    int F(int s, int l, int r) {
        for (int i = LOG-1; i >= 0; --i) {
            if (up[i][s] != C+1 && l <= W[up[i][s]] && W[up[i][s]] <= r)   s = up[i][s];
        }
        return s;
    }
} MN, MX;
struct bit {
    int b[N];
    void add(int p, int x) {
        for (; p < N; p |= (p + 1))   b[p] += x;
    }
    int sum(int r) {
        int S = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)   S += b[r];
        return S;
    }
    int sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }
} T;
bool cmp(array<int, 4> &A, array<int, 4> &B) {
    if (A[0] / SQ != B[0] / SQ)   return A[0] / SQ < B[0] / SQ;
    return A[1] < B[1];
}
bool cmp1(array<int, 2> &A, array<int, 2> &B) {
    return max(A[0], A[1]) < max(B[0], B[1]);
}
bool cmp2(array<int, 2> &A, array<int, 2> &B) {
    return min(A[0], A[1]) > min(B[0], B[1]);
}
vector<int> check_validity(int n, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    MN.init(n); MX.init(n); MN.fl = 0, MX.fl = 1;
    int q = S.size(), m = X.size();
    array<int, 2> e[m];
    for (int i = 0; i < m; ++i) e[i] = {X[i], Y[i]};
    sort(e, e+m, cmp1);
    for (int i = 0; i < m; ++i) MN.unite(e[i][0], e[i][1]);
    sort(e, e+m, cmp2);
    for (int i = 0; i < m; ++i) MX.unite(e[i][0], e[i][1]);
    MX.init2(); MN.init2();
    array<int, 4> qu[q];
    for (int i = 0; i < q; ++i) {
        int x = MX.F(S[i], L[i], n-1);
        qu[i] = {MX.tin[x], MX.tout[x], E[i], i};
        int y = MN.F(E[i], 0, R[i]);
        // cout << MX.tin[x] << ' ' << MX.tout[x] << ' ' << MN.tin[y] << ' ' << MN.tout[y] << '\n';
    }
    // for (int i = 1; i <= MX.tm; ++i)    cout << MX.a[i] << ' ';
    // cout << '\n';
    // for (int i = 1; i <= MN.tm; ++i)    cout << MN.a[i] << ' ';
    // cout << '\n';
    sort(qu, qu + q, cmp);
    int r = -1, l = 0;
    vector<int> ans(q);
    for (int i = 0; i < q; ++i) {
        while (r > qu[i][1]) {
            if (MX.a[r] < n)    T.add(MN.tin[MX.a[r]], -1);
            --r;
        }
        while (r < qu[i][1]) {
            ++r;
            if (MX.a[r] < n)    T.add(MN.tin[MX.a[r]], 1);
        }
        while (l > qu[i][0]) {
            --l;
            if (MX.a[l] < n)    T.add(MN.tin[MX.a[l]], 1);
        }
        while (l < qu[i][0]) {
            if (MX.a[l] < n)    T.add(MN.tin[MX.a[l]], -1);
            ++l;
        }
        int x = MN.F(qu[i][2], 0, R[qu[i][3]]);
        ans[qu[i][3]] = T.sum(MN.tin[x], MN.tout[x]) > 0;
    }
    return ans;
}

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