Submission #894184

#	Time	Username	Problem	Language	Result	Execution time	Memory
894184		box	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	150 ms	29524 KiB

catdog

#ifndef LOCAL
#include "catdog.h"
#endif
#include <bits/stdc++.h>
using namespace std;

#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;

const int MAXN = 1e5;
const int INF = 1e6;

int N;
vector<int> adj[MAXN];
bool has[MAXN][2];
int root[MAXN], depth[MAXN], child[MAXN], parent[MAXN], sz[MAXN];
ar<i64, 2> light[MAXN];

using info = ar<ar<int, 2>, 2>;

info operator+(const info one, const info two) {
    info me;
    for (int x : {0,1}) for (int y : {0,1})
        me[x][y] = min(INF,
            min(min(one[x][0] + two[0][y], one[x][1] + two[1][y]),
            1 + min(one[x][0] + two[1][y], one[x][1] + two[0][y])));
    return me;
}

struct segt {
    int l, r;
    segt *lc, *rc;
    info x;
    segt(int l, int r) : l(l), r(r) {
        if (l < r) {
            int m = (l + r) / 2;
            lc = new segt(l, m);
            rc = new segt(m + 1, r);
            x = lc->x + rc->x;
        } else x[1][0] = x[0][1] = INF, x[0][0] = x[1][1] = 0;
    }
    void upd(int i, const ar<int, 2> &v) {
        if (l == r) x[0][0] = v[0], x[1][1] = v[1];
        else {
            i <= lc->r ? lc->upd(i, v) : rc->upd(i, v);
            x = lc->x + rc->x;
        }
    }
    ar<int, 2> pack() {
        return {min(x[0][0], x[0][1]), min(x[1][0], x[1][1])};
    }
} *tree[MAXN];

int dfs_sz(int i) {
    int s = 1, x = 0;
    child[i] = -1;
    for (int j : adj[i]) if (parent[i] != j) {
        depth[j] = depth[i] + 1;
        parent[j] = i;
        int y = dfs_sz(j);
        if (y > x) {
            x = y;
            child[i] = j;
        }
        s += y;
    }
    return s;
}

void dfs_hvy(int r, int i) {
    ++sz[root[i] = r];
    if (~child[i]) dfs_hvy(r, child[i]);
    for (int j : adj[i]) if (parent[i] != j && child[i] != j) dfs_hvy(j, j);
}

void initialize(int N, vector<int> A, vector<int> B) {
    for (int h = 0; h < N - 1; h++) {
        auto [i, j] = make_pair(A[h], B[h]);
        i--, j--;
        adj[i].push_back(j);
        adj[j].push_back(i);
    }
    parent[0] = -1;
    dfs_sz(0);
    dfs_hvy(0, 0);
    for (int i = 0; i < N; i++) if (sz[i]) tree[i] = new segt(0, sz[i] - 1);
}

int pul(int i) {
    while (~i) {
        int r = root[i];
        int p = parent[r];
        if (~p) {
            auto v = tree[r]->pack();
            light[p][0] -= min(v[0], v[1] + 1), light[p][1] -= min(v[0] + 1, v[1]);
        }
        tree[r]->upd(depth[i] - depth[r], {int(min(light[i][0], i64(INF))), int(min(light[i][1], i64(INF)))});
        if (~p) {
            auto v = tree[r]->pack();
            light[p][0] += min(v[0], v[1] + 1), light[p][1] += min(v[0] + 1, v[1]);
        }
        i = p;
    }
    auto v = tree[0]->pack();
    return min(v[0], v[1]);
}

int cat(int i) {
    i--;
    has[i][0] = 1;
    light[i][0] += INF;
    return pul(i);
}

int dog(int i) {
    i--;
    has[i][1] = 1;
    light[i][1] += INF;
    return pul(i);
}

int neighbor(int i) {
    i--;
    if (has[i][0]) light[i][0] -= INF, has[i][0] = 0;
    if (has[i][1]) light[i][1] -= INF, has[i][1] = 0;
    return pul(i);
}

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