Submission #1196424

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196424		icebear	Werewolf (IOI18_werewolf)	C++20	0 / 100	912 ms	166472 KiB

werewolf

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

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;

template<class T>
    bool minimize(T &a, const T &b) {
        if (a > b) return a = b, true;
        return false;
    }

template<class T>
    bool maximize(T &a, const T &b) {
        if (a < b) return a = b, true;
        return false;
    }

#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORR(i,a,b) for(int i=(a); i>=(b); --i)
#define REP(i, n) for(int i=0; i<(n); ++i)
#define RED(i, n) for(int i=(n)-1; i>=0; --i)
#define MASK(i) (1LL << (i))
#define BIT(S, i) (((S) >> (i)) & 1)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define task "icebearat"

const int MOD = 1e9 + 7;
const int inf = 1e9 + 27092008;
const ll INF = 1e18 + 27092008;
const int N = 4e5 + 5;
vector<int> initG[N];

class SegmentTree {
private:
    int sizeTree;
    vector<int> nodes;

    int getSum(int id, int l, int r, int u, int v) {
        if (l > v || r < u) return 0;
        if (u <= l && r <= v) return nodes[id];
        int mid = (l + r) >> 1;
        return getSum(id << 1, l, mid, u, v) + getSum(id << 1 | 1, mid + 1, r, u, v);
    }

public:
    SegmentTree(int n = 0): sizeTree(n), nodes(4 * n + 5) {}
    void update(int pos, int value) {
        int id = 1, l = 1, r = sizeTree;
        while(l < r) {
            int mid = (l + r) >> 1;
            if (pos > mid) id = (id << 1 | 1), l = mid + 1;
            else id = (id << 1), r = mid;
        }
        nodes[id] += value;
        while(id) {
            id >>= 1;
            nodes[id] = nodes[id << 1] + nodes[id << 1 | 1];
        }
    }

    int getSum(int u, int v) {
        return getSum(1, 1, sizeTree, u, v);
    }
} IT;

struct DSU_tree {
    int node;
    vector<int> par, value;
    vector<vector<int>> G;
    DSU_tree(int n = 0): node(n), par(2 * n + 5), value(2 * n + 5), G(2 * n + 5) {
        FOR(i, 0, n) par[i] = i;
    }

    int root(int v) {
        return (par[v] == v ? v : par[v] = root(par[v]));
    }

    void unite(int u, int v) {
        int tmp = u;
        u = root(u); v = root(v);
        if (u == v) return;
        node++;
        par[u] = par[v] = par[node] = node;
        value[node] = tmp;
        G[node].pb(u);
        G[node].pb(v);
//        cout << node << ' ' << u << '\n';
//        cout << node << ' ' << v << '\n';
    }
} DST_from_S, DST_from_E;

struct Query {
    int U, V; // range of second subtree
    int id;
    Query(int u = 0, int v = 0, int i = 0):
        U(u), V(v), id(i) {}
};
vector<Query> del[N], add[N];

int parS[18][N], tinS[N], toutS[N], e_tourS[N], timerS = 0;
int parE[18][N], tinE[N], toutE[N], e_tourE[N], timerE = 0;

void dfs_S(int u) {
    tinS[u] = ++timerS;
    e_tourS[timerS] = u;
    for(int v : DST_from_S.G[u]) {
        parS[0][v] = u;
        dfs_S(v);
    }
    toutS[u] = timerS;
}

void dfs_E(int u) {
    tinE[u] = ++timerE;
    e_tourE[timerE] = u;
    for(int v : DST_from_E.G[u]) {
        parE[0][v] = u;
        dfs_E(v);
    }
    toutE[u] = timerE;
}

void build_DSUtree_from_S(int N) {
    DST_from_S = DSU_tree(N - 1);
    RED(i, N) for(int v : initG[i])
        if (v > i)
            DST_from_S.unite(i, v);
    memset(parS, -1, sizeof parS);
    dfs_S(DST_from_S.node);
    FOR(j, 1, 17) REP(i, DST_from_S.node)
        parS[j][i] = parS[j - 1][parS[j - 1][i]];
}

void build_DSUtree_from_E(int N) {
    DST_from_E = DSU_tree(N - 1);
    REP(i, N) for(int v : initG[i])
        if (v < i)
            DST_from_E.unite(i, v);
    memset(parE, -1, sizeof parE);
    dfs_E(DST_from_E.node);
    FOR(j, 1, 17) REP(i, DST_from_E.node)
        parE[j][i] = parE[j - 1][parE[j - 1][i]];
}

int findRoot_from_S(int u, int lower) { // find node contains component using all nodes >= lower
    RED(j, 18) if (parS[j][u] != -1 && DST_from_S.value[parS[j][u]] >= lower)
        u = parS[j][u];
    return u;
}

int findRoot_from_E(int u, int upper) { // find node contains component with all nodes <= upper
    RED(j, 18) if (parE[j][u] != -1 && DST_from_E.value[parE[j][u]] <= upper)
        u = parE[j][u];
    return u;
}

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();
    REP(i, M) {
        initG[X[i]].pb(Y[i]);
        initG[Y[i]].pb(X[i]);
    }
//    cout << "S TREE:\n";
    build_DSUtree_from_S(N);
//    cout << "E TREE:\n";
    build_DSUtree_from_E(N);

    REP(i, Q) {
        int subtree_S = findRoot_from_S(S[i], L[i]);
        int subtree_E = findRoot_from_E(E[i], R[i]);

        int L = tinS[subtree_S], R = toutS[subtree_S];
        int U = tinE[subtree_E], V = toutE[subtree_E];
//        cout << subtree_S << ' ' << L << ' ' << R << '\n';
//        cout << subtree_E << ' ' << U << ' ' << V << '\n';
        // check if there is a common value in e_tourS[L...R] and e_tourE[U...V]
        del[L - 1].emplace_back(U, V, i);
        add[R].emplace_back(U, V, i);
    }

//    REP(i, DST_from_S.node)
//        cout << "Node " << i << " : " << tinS[i] << ' ' << toutS[i] << ' ' << tinE[i] << ' ' << toutE[i] << '\n';

    vector<int> ans(Q);
    IT = SegmentTree(DST_from_S.node);
    FOR(i, 1, DST_from_S.node + 1) {
        int node = e_tourS[i];
        if (node < N) {
            IT.update(tinE[node], +1);
        }

        // sum(L, R) = sum(1, R) - sum(1, L - 1)
        for(auto query : del[i]) ans[query.id] -= IT.getSum(query.U, query.V);
        for(auto query : add[i]) ans[query.id] += IT.getSum(query.U, query.V);
    }

    for(int &i : ans) i = min(i, 1);
    return ans;
}

// int main() {
//     ios_base::sync_with_stdio(0);
//     cin.tie(0); cout.tie(0);
// //    vector<int> ans = check_validity(6, {5, 1, 1, 3, 3, 5}, {1, 2, 3, 4, 0, 2},
// //                                        {4, 4, 5}, {2, 2, 4}, {1, 2, 3}, {2, 2, 4});
//     vector<int> ans = check_validity(10, {6, 1, 8, 2, 9, 2, 8, 6, 3},
//                     {7, 5, 0, 9, 4, 7, 5, 0, 4}, {4, 8, 1, 8, 8, 0, 9, 1, 9, 9},
//                 {9, 1, 8, 3, 9, 1, 0, 7, 4, 5}, {0, 8, 1, 5, 3, 0, 6, 1, 5, 0}, {9, 9, 8, 5, 9, 2, 6, 8, 6, 9});
//     for(int x : ans) cout << x << ' ';
//     return 0;
// }

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