Submission #401580

#	Time	Username	Problem	Language	Result	Execution time	Memory
401580		timmyfeng	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	347 ms	38340 KiB

catdog

#include <bits/stdc++.h>
using namespace std;

const int N = 100001;

struct segtree {
    segtree *left, *right;
    array<long long, 4> mini;

    void pull() {
        mini = {N, N, N, N};
        for (int i = 0; i < 4; ++i) {
            for (int j = 0; j < 4; ++j) {
                int k = i / 2 * 2 + j % 2;
                mini[k] = min(mini[k], left->mini[i] + right->mini[j] + (i % 2 != j / 2));
            }
        }
    }

    segtree(int l, int r) {
        if (l == r) {
            mini = {0, N, N, 0};
        } else {
            int m = (l + r) / 2;
            left = new segtree(l, m);
            right = new segtree(m + 1, r);
            pull();
        }
    }

    void update(int a, long long x, long long y, int l, int r) {
        if (l == r) {
            mini[0] += x;
            mini[3] += y;
        } else {
            int m = (l + r) / 2;
            if (a <= m) {
                left->update(a, x, y, l, m);
            } else {
                right->update(a, x, y, m + 1, r);
            }
            pull();
        }
    }
};

int par[N], sub[N], in[N], head[N], tail[N];
segtree *path[N];

vector<int> adj[N];
int type[N];

void dfs_sub(int u) {
    sub[u] = 1;
    for (auto &c : adj[u]) {
        adj[c].erase(find(adj[c].begin(), adj[c].end(), u));
        par[c] = u;

        dfs_sub(c);
        sub[u] += sub[c];
        if (sub[c] > sub[adj[u][0]]) {
            swap(adj[u][0], c);
        }
    }
}

void dfs_hld(int u) {
    sub[u] = 0;
    for (auto c : adj[u]) {
        if (c == adj[u][0]) {
            head[c] = head[u];
            in[c] = in[u] + 1;
        } else {
            head[c] = c;
        }
        dfs_hld(c);
    }
    ++sub[head[u]];
}

array<long long, 2> get(array<long long, 4> &a) {
    long long x = min(a[0], a[1]), y = min(a[2], a[3]);
    return {min(x, y + 1), min(x + 1, y)};
}

void dfs_build(int u) {
    if (head[u] == u) {
        path[u] = new segtree(0, sub[u] - 1);
    }

    for (auto c : adj[u]) {
        dfs_build(c);
    }

    if (head[u] == u && u > 1) {
        array<long long, 2> mini = get(path[u]->mini);
        int p = par[u], v = head[p];
        path[v]->update(in[p], mini[0], mini[1], 0, sub[v] - 1);
    }
}

void update(int u, long long x, long long y) {
    while (u > 0) {
        int v = head[u];

        array<long long, 2> prv = get(path[v]->mini);
        path[v]->update(in[u], x, y, 0, sub[v] - 1);
        array<long long, 2> cur = get(path[v]->mini);

        u = par[v];
        x = cur[0] - prv[0];
        y = cur[1] - prv[1];
    }
}

long long query() {
    array<long long, 4> mini = path[1]->mini;
    return *min_element(mini.begin(), mini.end());
}

void initialize(int n, vector<int> a, vector<int> b) {
    for (int i = 0; i < n - 1; ++i) {
        adj[a[i]].push_back(b[i]);
        adj[b[i]].push_back(a[i]);
    }

    fill(type, type + n + 1, -1);

    head[1] = 1;

    dfs_sub(1);
    dfs_hld(1);
    dfs_build(1);
}

int cat(int u) {
    update(u, 0, N);
    type[u] = 0;
    return query();
}

int dog(int u) {
    update(u, N, 0);
    type[u] = 1;
    return query();
}

int neighbor(int u) {
    if (type[u] == 0) {
        update(u, 0, -N);
    } else {
        update(u, -N, 0);
    }
    type[u] = -1;
    return query();
}

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