Submission #680639

#	Time	Username	Problem	Language	Result	Execution time	Memory
680639		nutella	Cats or Dogs (JOI18_catdog)	C++17	0 / 100	7 ms	11476 KiB

catdog

#include <bits/stdc++.h>
#include "catdog.h"

using namespace std;

int n;

constexpr int N = 100001;

vector<int> g[N];

int head[N], sz[N], parent[N], tin[N], T = 0, hld_sz[N], type[N];

int ans = 0;

array<int, 3> sum[N];

void dfs_init(int v) {
    auto it = find(g[v].begin(), g[v].end(), parent[v]);
    if (it != g[v].end()) {
        g[v].erase(it);
    }

    sz[v] = 1;
    for (int &to: g[v]) {
        parent[to] = v;
        dfs_init(to);
        sz[v] += sz[to];
        if (sz[to] > sz[g[v][0]]) {
            swap(to, g[v][0]);
        }
    }
}

void dfs_hld(int v) {
    if (head[v] == 0) {
        head[v] = v;
    }
    hld_sz[head[v]] += 1;
    tin[v] = T++;
    for (int &to: g[v]) {
        if (to == g[v][0]) {
            head[to] = head[v];
        }
        dfs_hld(to);
    }
}

struct Info {
    int dp[3][3]{}, dq[3]{};

    Info() = default;

    Info(array<int, 3> d) {
        memset(dp, 0x3f, sizeof(dp));
        for (int i = 0; i < n; ++i) {
            dq[i] = d[i];
        }
    }
    Info(const int d[3][3], const int dk[3]) {
        memcpy(dp, d, sizeof(dp));
        memcpy(dq, dk, sizeof(dq));
    }
};

Info operator+(Info &a, Info &b) {
    int best[3];
    memset(best, 0x3f, sizeof(best));
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            best[i] = min(best[i], a.dp[i][j]);
        }
    }
    int dp[3][3], dq[3];
    for (int i = 0; i < 3; ++i) {
        dq[i] = min(0x3f3f3f3f, a.dq[i] + b.dq[i]);
    }
    memset(dp, 0x3f, sizeof(dp));
    for (int x = 0; x < 3; ++x) {
        for (int y = 0; y < 3; ++y) {
            for (int z = 0; z < 3; ++z) {
                dp[x][z] = min({dp[x][z], a.dp[x][y] + b.dp[y][z],
                                best[x] + b.dp[y][z] + (y != 2), a.dp[x][y] + b.dq[z] + (z != y),
                                a.dq[x] + b.dp[y][z] + (z != y)});
            }
            dp[x][y] = min({dp[x][y], a.dp[x][y] + b.dq[2], a.dq[2] + b.dp[x][y], a.dq[x] + b.dq[y] + 1});
        }
    }
    return {dp, dq};
}

struct SegmentTree {
    vector<Info> t;
    int n{};

    void init(int m) {
        n = 1 << (__lg(m) + bool(m & (m - 1)));
        t.assign(2 * n, {});
    }

    void modify(int i, Info x) {
        for (t[i += n] = x; i >>= 1;) {
            t[i] = t[i << 1] + t[i << 1 | 1];
        }
    }

    array<int, 3> ans() {
        array<int, 3> ans{};
        for (int i = 0; i < 3; ++i) {
            ans[i] = min({t[1].dp[i][0], t[1].dp[i][1], t[1].dp[i][2], t[1].dq[i]});
        }
        int mn = min({ans[0], ans[1], ans[2]});
        for (int i = 0; i < 3; ++i) {
            ans[i] = min(ans[i], mn + 1);
        }
        return ans;
    }

    int best() {
        int ans = numeric_limits<int>::max();
        for (int i = 0; i < 3; ++i) {
            ans = min({ans, t[1].dp[i][0], t[1].dp[i][1], t[1].dp[i][2], t[1].dq[i]});
        }
        return ans;
    }
};

SegmentTree t[N];

void update(int v) {
    while (true) {
        int p = head[v];
        if (p != 0) {
            auto kek = t[p].ans();
            for (int i = 0; i < 3; ++i) {
                sum[parent[p]][i] -= kek[i];
            }
        }
        array<int, 3> now{};
        if (type[v] == 2) {
            now = sum[v];
        } else {
            now[0] = now[1] = now[2] = 0x3f3f3f3f;
            now[type[v]] = sum[v][type[v]];
        }
        t[head[v]].modify(tin[v] - tin[head[v]], now);
        if (p != 0) {
            auto kek = t[p].ans();
            for (int i = 0; i < 3; ++i) {
                sum[parent[p]][i] += kek[i];
            }
            v = parent[p];
        } else {
            break;
        }
    }
}

void initialize(int N, std::vector<int> A, std::vector<int> B) {
    n = N;

    for (int i = 0; i < n - 1; ++i) {
        g[A[i]].push_back(B[i]);
        g[B[i]].push_back(A[i]);
    }

    dfs_init(1);
    dfs_hld(1);

    for (int i = 1; i <= n; ++i) {
        if (head[i] == i) {
            t[i].init(hld_sz[i]);
        }
    }
}

int cat(int v) {
    type[v] = 0;

    update(v);

    return t[1].best();
}

int dog(int v) {
    type[v] = 1;

    update(v);

    return t[1].best();
}

int neighbor(int v) {
    type[v] = 2;

    update(v);

    return t[1].best();
}

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