Submission #102586

#	Time	Username	Problem	Language	Result	Execution time	Memory
102586		minhtung0404	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	1465 ms	19192 KiB

catdog

#include "catdog.h"
#include<bits/stdc++.h>
const int N = 1e5 + 5;
using namespace std;

void up(int&a, int b){
    if (a > b) a = b;
}

struct nodeIT{
    int a[2][2];

    int Min(int x){
        int ans = a[0][0] + (x == 0);
        for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) up(ans, a[i][j] + (x == i));
        return ans;
    }

//    void out(){
//        for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) cout << a[i][j] << " "; cout << "\n";
//    }
} it[N << 2], zero;

typedef vector <int> vi;
vi G[N];
int n, num[N], p[N], chainidx[N], chainst[N], chainen[N], nchain;
int node[N], pos[N], cnt, dp[N][2];
int ani[N];

nodeIT Merge(nodeIT le, nodeIT ri){
    nodeIT ans;
    for (int i = 0; i < 2; i++){
        for (int j = 0; j < 2; j++){
            ans.a[i][j] = N;
            for (int k = 0; k < 2; k++){
                for (int h = 0; h < 2; h++){
                    up(ans.a[i][j], le.a[i][k] + ri.a[h][j] + (k != h));
                }
            }
        }
    }
    return ans;
}

void update(int i, int l, int r, int pos, int v1, int v2){
    if (l > pos || pos > r) return;
    if (l == r){
        it[i].a[0][0] = v1;
        it[i].a[1][1] = v2;
        it[i].a[0][1] = it[i].a[1][0] = N;
        return;
    }
    int mid = (l + r) >> 1;
    update(i << 1, l, mid, pos, v1, v2); update(i << 1 | 1, mid+1, r, pos, v1, v2);
    it[i] = Merge(it[i << 1], it[i << 1 | 1]);
//    cout << "st " << i << "\n";
//    it[i].out(); it[i << 1].out(); it[i << 1 | 1].out();
//    cout << "en " << i << "\n\n";
}

void init(int i, int l, int r){
    if (l == r){
        it[i] = zero;
        return;
    }
    int mid = (l + r) >> 1;
    init(i << 1, l, mid); init(i << 1 | 1, mid+1, r);
    it[i] = zero;
}

nodeIT get(int i, int l, int r, int L, int R){
    if (L > r || l > R) return zero;
    if (L <= l && r <= R) return it[i];
    int mid = (l + r) >> 1;
    return Merge(get(i << 1, l, mid, L, R), get(i << 1 | 1, mid+1, r, L, R));
}

void dfs(int u){
    num[u] = 1;
    for (auto v : G[u]){
        if (v == p[u]) continue;
        p[v] = u;
        dfs(v);
        num[u] += num[v];
    }
}

void hld(int u){
    pos[u] = ++cnt; node[cnt] = u;
    chainidx[u] = nchain;
    int Max = -1;
    for (auto v : G[u]){
        if (v == p[u]) continue;
        if (Max == -1 || num[Max] < num[v]) Max = v;
    }
    if (Max != -1) hld(Max);
    else chainen[nchain] = u;
    for (auto v : G[u]){
        if (v == p[u] || v == Max) continue;
        chainst[++nchain] = v;
        hld(v);
    }
}

void initialize(int N, vi A, vi B) {
    n = N;
    for (int i = 1; i <= n; i++) ani[i] = 2;
    for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) zero.a[i][j] = (i == j ? 0 : N);
    for (int i = 0; i < n-1; i++){
        G[A[i]].push_back(B[i]);
        G[B[i]].push_back(A[i]);
    }
    dfs(1);
    chainst[++nchain] = 1;
    hld(1); init(1, 1, n);
}

int cat(int v) {
    nodeIT cur; ani[v] = 0;
    while (v){
        int idx = chainidx[v], nxt = p[chainst[idx]];

        cur = get(1, 1, n, pos[chainst[idx]], pos[chainen[idx]]);
        dp[nxt][0] -= cur.Min(1); dp[nxt][1] -= cur.Min(0);

        update(1, 1, n, pos[v], ((ani[v] == 1) ? N : dp[v][0]), ((ani[v] == 0) ? N : dp[v][1]));

        cur = get(1, 1, n, pos[chainst[idx]], pos[chainen[idx]]);
        dp[nxt][0] += cur.Min(1); dp[nxt][1] += cur.Min(0);

        v = nxt;
    }
    return min(dp[0][0], dp[0][1]);
}

int dog(int v) {
    nodeIT cur; ani[v] = 1;
    while (v){
        int idx = chainidx[v], nxt = p[chainst[idx]];

        cur = get(1, 1, n, pos[chainst[idx]], pos[chainen[idx]]);
        dp[nxt][0] -= cur.Min(1); dp[nxt][1] -= cur.Min(0);

        update(1, 1, n, pos[v], ((ani[v] == 1) ? N : dp[v][0]), ((ani[v] == 0) ? N : dp[v][1]));

        cur = get(1, 1, n, pos[chainst[idx]], pos[chainen[idx]]);
        dp[nxt][0] += cur.Min(1); dp[nxt][1] += cur.Min(0);

        v = nxt;
    }
    return min(dp[0][0], dp[0][1]);
}

int neighbor(int v) {
    nodeIT cur; ani[v] = 2;
    while (v){
        int idx = chainidx[v], nxt = p[chainst[idx]];

        cur = get(1, 1, n, pos[chainst[idx]], pos[chainen[idx]]);
        dp[nxt][0] -= cur.Min(1); dp[nxt][1] -= cur.Min(0);

        update(1, 1, n, pos[v], ((ani[v] == 1) ? N : dp[v][0]), ((ani[v] == 0) ? N : dp[v][1]));

        cur = get(1, 1, n, pos[chainst[idx]], pos[chainen[idx]]);
        dp[nxt][0] += cur.Min(1); dp[nxt][1] += cur.Min(0);

        v = nxt;
    }
    return min(dp[0][0], dp[0][1]);
}

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