Submission #978695

#	Time	Username	Problem	Language	Result	Execution time	Memory
978695		peterandvoi	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	210 ms	27988 KiB

catdog

#include <bits/stdc++.h>

#include "catdog.h"

using namespace std;

#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif

template<class A, class B>
bool minz(A &a, const B &b) {
    return a > b ? a = b, true : false;
}

const int INF = int(1e9);

struct Node {
    int dat[2][2];

    Node() {
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {
                dat[i][j] = INF;
            }
        }
    }

    Node operator + (const Node &o) const {
        Node res;
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {
                if (dat[i][j] != INF) {
                    for (int ii = 0; ii < 2; ++ii) {
                        for (int jj = 0; jj < 2; ++jj) {
                            if (o.dat[ii][jj] != INF) {
                                int v = dat[i][j] + o.dat[ii][jj] + (j ^ ii);
                                minz(res.dat[i][jj], v);
                            }
                        }
                    }
                }
            }
        }
        return res;
    }
};

struct Segtree {
    int n;
    vector<Node> s;

    Segtree() {};

    Segtree(int n): n(n) {
        s.resize(4 << __lg(n), Node());
    }

    void bld(int id, int l, int r) {
        if (l == r) {
            s[id].dat[0][0] = 0;
            s[id].dat[1][1] = 0;
            return;
        }
        int md = (l + r) / 2;
        bld(id * 2, l, md);
        bld(id * 2 + 1, md + 1, r);
        s[id] = s[id * 2] + s[id * 2 + 1];
    }

    void bld() {
        bld(1, 1, n);
    }

    void upd(int i, int C, int D, int x) {
        int id = 1, l = 1, r = n;
        while (l ^ r) {
            int md = (l + r) / 2;
            id *= 2;
            if (i <= md) {
                r = md;
            } else {
                l = md + 1;
                id += 1;
            }
        }
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {
                s[id].dat[i][j] = INF;
            }
        }
        if (x != 0) {
            s[id].dat[0][0] = C;
        }
        if (x != 1) {
            s[id].dat[1][1] = D;
        }
        while (id > 1) {
            id /= 2;
            s[id] = s[id * 2] + s[id * 2 + 1];
        }
    }

    int get(int i) {
        return min(s[1].dat[i][0], s[1].dat[i][1]);
    }

    int res(int i) {
        return min(get(i), get(i ^ 1) + 1);
    }
};

const int N = int(1e5) + 5;

int n;
int pos[N], head[N], tail[N], sz[N], par[N], c[N];
int s[2][N], up[2][N];
vector<int> g[N];
Segtree tree[N];

void dfs(int u) {
    for (int &v : g[u]) {
        if (v == par[u]) {
            swap(v, g[u].back());
            g[u].pop_back();
            break;
        }
    }
    sz[u] = 1;
    for (int v : g[u]) {
        par[v] = u;
        dfs(v);
        sz[u] += sz[v];
    }
}

int order;

void hld(int u) {
    pos[u] = ++order;
    tail[head[u]] = order;
    if (g[u].size()) {
        int x = *max_element(g[u].begin(), g[u].end(), [&](int i, int j) {
            return sz[i] < sz[j];
        });
        head[x] = head[u];
        hld(x);
        for (int v : g[u]) {
            if (v ^ x) {
                head[v] = v;
                order = 0;
                hld(v);
            }
        }
    }
}

void app(int u) {
    while (head[u] != 1) {
        u = head[u];
        int p = par[u];
        for (int i = 0; i < 2; ++i) {
            up[i][p] -= s[i][u];
            s[i][u] = tree[u].res(i);
            up[i][p] += s[i][u];
        }
        tree[head[p]].upd(pos[p], up[0][p], up[1][p], c[p]);
        u = p;
    }
}

int upd(int v, int x) {
    c[v] = x;
    tree[head[v]].upd(pos[v], up[0][v], up[1][v], c[v]);
    app(v);
    return min(tree[1].get(0), tree[1].get(1));
}

int cat(int v) {
    return upd(v, 1);
}

int dog(int v) {
    return upd(v, 0);
}

int neighbor(int v) {
    return upd(v, 2);
}

void initialize(int x, std::vector<int> A, std::vector<int> B) {
    n = x;
    for (int i = 0; i + 1 < n; ++i) {
        int u = A[i], v = B[i];
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    dfs(1);
    head[1] = 1;
    hld(1);
    for (int i = 1; i <= n; ++i) {
        c[i] = 2;
        if (tail[i]) {
            tree[i] = Segtree(tail[i]);
            tree[i].bld();
        }
    }
}

#ifdef ngu
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
    int n;
    cin >> n;
    vector<int> A, B;
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        A.emplace_back(u);
        B.emplace_back(v);
    }
    initialize(n, A, B);
    int q;
    cin >> q;
    while (q--) {
        int type, v;
        cin >> type >> v;
        cout << upd(v, type) << "\n";
    }
}
#endif

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