Submission #1216437

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216437		badge881	Cats or Dogs (JOI18_catdog)	C++20	100 / 100	112 ms	26440 KiB

catdog

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

const int MAX = 1e5 + 5;

int N, sz[MAX], head[MAX], par[MAX], heavy[MAX], pos[MAX], sz_chain[MAX], t[MAX];
vector<int> adj[MAX];

struct node
{
    int a[2][2];
    node()
    {
        for (int i = 0; i < 2; ++i)
            for (int j = 0; j < 2; ++j)
                a[i][j] = MAX;
    }

    friend node operator+(const node &a, const node &b)
    {
        node c;
        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)
                        c.a[i][l] = min(c.a[i][l], a.a[i][j] + b.a[k][l] + (k != j));
        return c;
    }
};

struct segment_tree
{
    vector<node> st;
    segment_tree(int n) : st(n << 2) {}
    segment_tree() : st(0) {}

    void update(int id, int l, int r, int pos, int v_cat, int v_dog)
    {
        if (l == r)
        {
            st[id].a[0][0] += v_cat;
            st[id].a[1][1] += v_dog;
        }
        else
        {
            int mid = l + r >> 1;
            if (pos <= mid)
                update(id << 1, l, mid, pos, v_cat, v_dog);
            else
                update(id << 1 | 1, mid + 1, r, pos, v_cat, v_dog);
            st[id] = st[id << 1] + st[id << 1 | 1];
        }
    }

    void build(int id, int l, int r)
    {
        if (l == r)
        {
            st[id].a[0][0] = 0;
            st[id].a[1][1] = 0;
            st[id].a[0][1] = MAX;
            st[id].a[1][0] = MAX;
        }
        else
        {
            int mid = l + r >> 1;
            build(id << 1, l, mid);
            build(id << 1 | 1, mid + 1, r);
            st[id] = st[id << 1] + st[id << 1 | 1];
        }
    }

    node get()
    {
        return st[1];
    }
} chains[MAX];

void dfs_sz(int u)
{
    sz[u] = 1;
    for (int v : adj[u])
    {
        adj[v].erase(find(adj[v].begin(), adj[v].end(), u));
        par[v] = u;
        dfs_sz(v);
        sz[u] += sz[v];
        if (sz[heavy[u]] < sz[v])
            heavy[u] = v;
    }
}

void dfs_hld(int u, int hd)
{
    head[u] = hd;
    pos[u] = ++sz_chain[hd];
    if (heavy[u])
    {
        dfs_hld(heavy[u], hd);
        for (int v : adj[u])
            if (v != heavy[u])
                dfs_hld(v, v);
    }
}

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

    dfs_sz(1);
    dfs_hld(1, 1);

    for (int i = 1; i <= N; ++i)
    {
        if (head[i] == i)
        {
            chains[i] = segment_tree(sz_chain[i]);
            chains[i].build(1, 1, sz_chain[i]);
        }
    }
}

void modify(int u, int cat, int dog)
{
    while (u > 0)
    {
        node cur = chains[head[u]].get();
        int fcat = min({cur.a[0][0], cur.a[0][1], cur.a[1][0] + 1, cur.a[1][1] + 1});
        int fdog = min({cur.a[1][0], cur.a[1][1], cur.a[0][0] + 1, cur.a[0][1] + 1});

        chains[head[u]].update(1, 1, sz_chain[head[u]], pos[u], cat, dog);
        cur = chains[head[u]].get();

        int gcat = min({cur.a[0][0], cur.a[0][1], cur.a[1][0] + 1, cur.a[1][1] + 1});
        int gdog = min({cur.a[1][0], cur.a[1][1], cur.a[0][0] + 1, cur.a[0][1] + 1});

        cat = gcat - fcat;
        dog = gdog - fdog;
        u = par[head[u]];
    }
}

int answer()
{
    node cur = chains[1].get();
    int cat = min(cur.a[0][0], cur.a[0][1]);
    int dog = min(cur.a[1][0], cur.a[1][1]);
    return min(cat, dog);
}

int cat(int u)
{
    modify(u, 0, MAX);
    t[u] = 1;
    return answer();
}

int dog(int u)
{
    modify(u, MAX, 0);
    t[u] = 2;
    return answer();
}

int neighbor(int u)
{
    if (t[u] == 1)
        modify(u, 0, -MAX);
    if (t[u] == 2)
        modify(u, -MAX, 0);
    t[u] = 0;
    return answer();
}

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