Submission #1270193

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270193		MisterReaper	Cats or Dogs (JOI18_catdog)	C++20	0 / 100	0 ms	328 KiB

catdog

// 15:59
#include "bits/stdc++.h"
#include "catdog.h"

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

using i64 = long long;

constexpr i64 inf = i64(1E9);

using M = std::array<std::array<i64, 2>, 2>;

M operator+ (M lhs, M rhs) {
    M res {};
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            res[i][j] = std::min({lhs[i][0] + rhs[0][j], 
                                  lhs[i][0] + rhs[1][j] + 1, 
                                  lhs[i][1] + rhs[0][j] + 1, 
                                  lhs[i][1] + rhs[1][j]});
        }
    }
    return res;
}

#define def int mid = (l + r) >> 1, lv = v + 1, rv = v + ((mid - l + 1) << 1)

struct segtree {
    int n;
    std::vector<M> tree;
    segtree() {}
    segtree(int n_) : n(n_), tree(n << 1) {
        auto dfs = [&](auto&& self, int v, int l, int r) -> void {
            if (l == r) {
                tree[v] = {0, inf, inf, 0};
                return;
            }
            def;
            self(self, lv, l, mid);
            self(self, rv, mid + 1, r);
            tree[v] = tree[lv] + tree[rv];
        };
        dfs(dfs, 0, 0, n - 1);
    }
    void init(int n_) {
        n = n_;
        tree.assign(n << 1, {});
        auto dfs = [&](auto&& self, int v, int l, int r) -> void {
            if (l == r) {
                tree[v] = {0, inf, inf, 0};
                return;
            }
            def;
            self(self, lv, l, mid);
            self(self, rv, mid + 1, r);
            tree[v] = tree[lv] + tree[rv];
        };
        dfs(dfs, 0, 0, n - 1);
    }
    void modify(int v, int l, int r, int p, int k, i64 x) {
        if (l == r) {
            tree[v][k >> 1][k & 1] += x;
            return;
        }
        def;
        if (p <= mid) {
            modify(lv, l, mid, p, k, x);
        } else {
            modify(rv, mid + 1, r, p, k, x);
        }
        tree[v] = tree[lv] + tree[rv];
    }
    void modify(int p, int k, i64 x) {
        modify(0, 0, n - 1, p, k, x);
    }
    M get(int v, int l, int r, int ql, int qr) {
        if (ql == l && r == qr) {
            return tree[v];
        }
        def;
        if (qr <= mid) {
            return get(lv, l, mid, ql, qr);
        } else if (mid + 1 <= ql) {
            return get(rv, mid + 1, r, ql, qr);
        } else {
            return get(lv, l, mid, ql, mid)
                 + get(rv, mid + 1, r, mid + 1, qr);
        }
    }
    M get(int l, int r) {
        return get(0, 0, n - 1, l, r);
    }
} seg;

int tim;
std::vector<int> tp;
std::vector<int> siz, par, top, tin, len;
std::vector<std::vector<int>> adj;

void dfs1(int v) {
    for (auto& u : adj[v]) {
        adj[u].erase(std::find(adj[u].begin(), adj[u].end(), v));
        par[u] = v;
        dfs1(u);
        siz[v] += siz[u];
        if (siz[u] > siz[adj[v][0]]) {
            std::swap(adj[v][0], u);
        }
    }
}

void dfs2(int v) {
    len[top[v]]++;
    tin[v] = tim++;
    for (auto& u : adj[v]) {
        top[u] = (u == adj[v][0] ? top[v] : u);
        dfs2(u);
    }
}

void initialize(int N, std::vector<int> A, std::vector<int> B) {
    tp.assign(N, 0);
    siz.assign(N, 1);
    par.assign(N, 0);
    top.assign(N, {});
    tin.assign(N, 0);
    len.assign(N, 0);
    adj.assign(N, {});
    seg.init(N);
    for (int i = 0; i < N - 1; ++i) {
        --A[i], --B[i];
        adj[A[i]].emplace_back(B[i]);
        adj[B[i]].emplace_back(A[i]);
    }

    debug(0);
    dfs1(0);
    debug(1);
    dfs2(0);
    debug(2);
}

void add(int v, int t) {
    debug("add", v, t);
    int u = v;
    while (top[u] != 0) {
        if (u == top[u]) {
            M x = seg.get(tin[u], tin[u] + len[u] - 1);
            debug(x);
            seg.modify(tin[par[u]], 0, t * std::min({x[0][0], x[0][1], x[1][0] + 1, x[1][1] + 1}));
            seg.modify(tin[par[u]], 3, t * std::min({x[0][0] + 1, x[0][1] + 1, x[1][0], x[1][1]}));
            u = par[u];
        } else {
            u = top[u];
        }
    }
}

int answer() {
    M res = seg.get(0, len[0] - 1);
    debug("answer", res);
    i64 ans = inf;
    for (int i = 0; i < 4; ++i) {
        ans = std::min(ans, res[i >> 1][i & 1]);
    }
    return ans;
}

int cat(int v) {
    debug("cat", v);
    --v;
    add(v, -1);
    tp[v] = 1;
    seg.modify(tin[v], 3, inf);
    add(v, +1);
    return answer();
}

int dog(int v) {
    debug("dog", v);
    --v;
    add(v, -1);
    tp[v] = 2;
    seg.modify(tin[v], 0, inf);
    add(v, +1);
    return answer();
}

int neighbor(int v) {
    debug("neighbor", v);
    --v;
    add(v, -1);
    if (tp[v] == 1) {
        seg.modify(tin[v], 3, -inf);
    } else if (tp[v] == 2) {
        seg.modify(tin[v], 0, -inf);
    } else {
        assert(false);
    }
    tp[v] = 0;
    add(v, +1);
    return answer();
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 30
• Subtask 3: 0 / 62