Submission #680637

#	Time	Username	Problem	Language	Result	Execution time	Memory
680637		nutella	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	328 ms	30144 KiB

catdog

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

using namespace std;
using ll = long long;

int n;

constexpr int N = 100001, inf = 1e9 + 7;

vector<int> g[N];

int head[N], sz[N], parent[N], tin[N], T = 0, hld_sz[N], type[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];
    }

    for (int i = 1; i < g[v].size(); ++i) {
        if (sz[g[v][i]] > sz[g[v][0]]) {
            swap(g[v][i], g[v][0]);
        }
    }
}

void dfs_hld(int v) {
    if (head[v] == 0) {
        head[v] = v;
    }

    tin[v] = T++;
    hld_sz[head[v]] += 1;

    for (int to : g[v]) {
        if (to == g[v][0]) {
            head[to] = head[v];
        }
        dfs_hld(to);
    }
}

struct Info {
    array<ll, 4> dp{0, inf, inf, 0};

    Info() = default;

    Info(array<ll, 4> d) : dp(d) {}
};

Info operator+(Info a, Info b) {
    Info res;
    fill(res.dp.begin(), res.dp.end(), inf);
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 4; ++j) {
            int x = (i & 2) + (j & 1);
            res.dp[x] = min(res.dp[x], a.dp[i] + b.dp[j] + ((i & 1) != bool(j & 2)));
        }
    }
    return res;
}

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, ll x, ll y) {
        i += n;
        t[i].dp[0] += x, t[i].dp[3] += y;
        while (i >>= 1) {
            t[i] = t[i << 1] + t[i << 1 | 1];
        }
    }
};

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

SegmentTree t[N];

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

        auto was = transform(t[u].t[1].dp);
        t[u].modify(tin[v] - tin[u], x, y);
        auto now = transform(t[u].t[1].dp);

        v = parent[u];
        x = now[0] - was[0];
        y = now[1] - was[1];
    }
}

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 query() {
    auto res = t[1].t[1].dp;
    return *min_element(res.begin(), res.end());
}

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

    update(v, 0, N);

    return query();
}

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

    update(v, N, 0);

    return query();
}

int neighbor(int v) {
    if (type[v] == 0) {
        update(v, 0, -N);
    } else {
        update(v, -N, 0);
    }

    type[v] = 2;

    return query();
}

Compilation message (stderr)

catdog.cpp: In function 'void dfs_init(int)':
catdog.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int i = 1; i < g[v].size(); ++i) {
      |                     ~~^~~~~~~~~~~~~

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