Submission #102578

#	Time	Username	Problem	Language	Result	Execution time	Memory
102578		minhtung0404	Cats or Dogs (JOI18_catdog)	C++17	0 / 100	5 ms	2688 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 ans = a[0][0];
        for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) up(ans, a[i][j]);
        return ans;
    }
} it[N << 2], zero;

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

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

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;
    chainind[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 = 0; i < 2; i++) for (int j = 0; j < 2; j++) zero.a[i][j] = 0;
    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) {
    update(1, 1, n, pos[v], N, 0);
    return get(1, 1, n, chainst[1], chainen[1]).Min();
}

int dog(int v) {
    update(1, 1, n, pos[v], 0, N);
    return get(1, 1, n, chainst[1], chainen[1]).Min();
}

int neighbor(int v) {
    update(1, 1, n, pos[v], 0, 0);
    return get(1, 1, n, chainst[1], chainen[1]).Min();
}

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