Submission #894154

#	Time	Username	Problem	Language	Result	Execution time	Memory
894154		box	Cats or Dogs (JOI18_catdog)	C++17	38 / 100	148 ms	20644 KiB

catdog

#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])));
    // cout << "ONE " << one[0][0] << ' ' << one[0][1] << ' ' << one[1][0] << ' ' << one[1][1] << endl;
    // cout << "TWO " << two[0][0] << ' ' << two[0][1] << ' ' << two[1][0] << ' ' << two[1][1] << endl;
    // cout << "ME " << me[0][0] << ' ' << me[0][1] << ' ' << me[1][0] << ' ' << me[1][1] << endl;
    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;
    }
    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;
        }
        // cout << l << " " << r << endl;
        // cout << "GOT " << x[0][0] << ' ' << x[0][1] << ' ' << x[1][0] << ' ' << x[1][1] << endl;
    }
    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) {
    // cout << "GOT " << i+1 << " => " << r+1 << endl;
    ++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);
        // cout << "at root " << i+1 << ", got size " << sz[i] << endl;
    }
}

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);
}

#ifdef LOCAL

int main() {
    int N;
    cin >> N;
    vector<int> A(N-1, 0), B(N-1, 0);
    for (int i = 0; i < N-1; i++) cin >> A[i] >> B[i];
    initialize(N, A, B);
    int Q;
    cin >> Q;
    while (Q--) {
        int t, i;
        cin >> t >> i;
        cout << (t == 1 ? cat : t == 2 ? dog : neighbor)(i) << '\n';
        // for (int i = 0; i < N; i++) cout << light[i][0] << ' ' << light[i][1] << '\n';
        // cout << endl;
    }
}

#endif

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