Submission #1293647

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293647		anngela	Cats or Dogs (JOI18_catdog)	C++20	100 / 100	159 ms	25784 KiB

catdog

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

const int MAXN = 1e5 + 5, INF = 1e9;
vector<int> adj[MAXN];
int sz[MAXN], head[MAXN], heavy[MAXN], fa[MAXN], pos[MAXN], pet[MAXN], len[MAXN];

struct Node {
    int b[2][2];
    Node()
    {
        b[0][0] = b[1][1] = 0;
        b[0][1] = b[1][0] = INF;
    }
};

Node Merge(Node const& a, Node const& b)
{
    Node res;
    res.b[0][0] = res.b[1][0] = res.b[0][1] = res.b[1][1] = INF;
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
                for (int l = 0; l < 2; l++)
                    res.b[i][l] = min(res.b[i][l], a.b[i][j] + b.b[k][l] + (j ^ k));

    return res;
}

struct SegTree {
    vector<Node> tree;

    void Init(int N)
    {
        tree.resize(N * 4);
    }

    void Update(int id, int l, int r, int p, int cat, int dog)
    {
        if (p < l || r < p) return;
        if (l == r)
        {
            tree[id].b[0][0] += cat;
            tree[id].b[1][1] += dog;
            return;
        }
        int mid = (l + r) >> 1;
        if (p <= mid)
            Update(id << 1, l, mid, p, cat, dog);
        else
            Update(id << 1 | 1, mid + 1, r, p, cat, dog);
        tree[id] = Merge(tree[id << 1], tree[id << 1 | 1]);
    }

    pair<int, int> Get()
    {
        Node ans = tree[1];
        int blocked_if_cat = min({ans.b[0][0], ans.b[0][1], ans.b[1][0] + 1, ans.b[1][1] + 1});
        int blocked_if_dog = min({ans.b[1][0], ans.b[1][1], ans.b[0][0] + 1, ans.b[0][1] + 1});
        return {blocked_if_cat, blocked_if_dog};
    }
} st[MAXN];

void Dfs(int u, int father)
{
    sz[u] = 1;
    for (int v : adj[u])
        if (v != father)
        {
            fa[v] = u;
            Dfs(v, u);
            sz[u] += sz[v];
            if (heavy[u] == 0 || sz[v] > sz[heavy[u]])
                heavy[u] = v;
        }
}

void Build(int u, int hd)
{
    head[u] = hd;
    pos[u] = ++len[hd];
    if (heavy[u])
        Build(heavy[u], hd);
    for (int v : adj[u])
        if (v != fa[u] && v != heavy[u])
            Build(v, v);
}

void initialize(int N, vector<int> A, vector<int> B)
{
    for (int i = 0; i < N - 1; i++)
    {
        adj[A[i]].emplace_back(B[i]);
        adj[B[i]].emplace_back(A[i]);
    }

    Dfs(1, 0);
    Build(1, 1);

    for (int i = 1; i <= N; i++)
        if (head[i] == i)
            st[head[i]].Init(len[head[i]]);
}


void UpdateChains(int u, int cat, int dog)
{
    while (u)
    {
        auto [c0, d0] = st[head[u]].Get();
        st[head[u]].Update(1, 1, len[head[u]], pos[u], cat, dog);
        auto [c1, d1] = st[head[u]].Get();
        cat = c1 - c0;
        dog = d1 - d0;
        u = fa[head[u]];
    }
}

enum {gol, pisica, caine};

int cat(int v)
{
    pet[v] = pisica;
    UpdateChains(v, 0, INF);
    Node res = st[1].tree[1];
    return min({res.b[0][0], res.b[0][1], res.b[1][0], res.b[1][1]});
}

int dog(int v)
{
    pet[v] = caine;
    UpdateChains(v, INF, 0);
    Node res = st[1].tree[1];
    return min({res.b[0][0], res.b[0][1], res.b[1][0], res.b[1][1]});
}

int neighbor(int v)
{
    if (pet[v] == pisica)
        UpdateChains(v, 0, -INF);
    else
        UpdateChains(v, -INF, 0);

    pet[v] = gol;
    Node res = st[1].tree[1];
    return min({res.b[0][0], res.b[0][1], res.b[1][0], res.b[1][1]});
}

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