Submission #1110505

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110505		BF001	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	1270 ms	36948 KiB

catdog

#include<bits/stdc++.h>
using namespace std;
 
#define NN 100005
#define oo 1e6
#define fi first 
#define se second

typedef pair<int, int> ii;

int n, q, st[NN], dep[NN], hed[NN], id[NN], siz[NN], par[NN], cnt = 0;
vector<int> adj[NN];

struct segtree{
    struct  node
    {
        int a[2][2];
        node(){
            for (int i = 0; i <= 1; i++){
                for (int j = 0; j <= 1; j++) a[i][j] = oo;
            }
        }
        node operator + (node& o){
            node rt;
            for (int l = 0; l <= 1; l++){
                for (int i = 0; i <= 1; i++){
                    for (int j = 0; j <= 1; j++){
                        for (int r = 0; r <= 1; r++){
                            rt.a[l][r] = min(rt.a[l][r], a[l][i] + o.a[j][r] + (i ^ j));
                        }   
                    }
                }
            }
            return rt;
        }
    };
    vector<node> bit;
    int si;
    void init(int n){
        si = n;
        bit.resize(4 * n + 5);
        build(1, 1, si);
    }
    void build(int id, int l, int r){
        if (l == r){
            bit[id].a[0][0] = bit[id].a[1][1] = 0;
            return;
        }
        int mid = (l + r) >> 1;
        build(id * 2, l, mid);
        build(id * 2 + 1, mid + 1, r);
        bit[id] = bit[id * 2] + bit[id * 2 + 1];
    }
    void ud(int id, int l, int r, int pos, int val, int val1){
        if (l > pos || r < pos) return;
        if (l == r){
            bit[id].a[0][0] += val;
            bit[id].a[1][1] += val1;
            return;
        }
        int mid = (l + r) >> 1;
        ud(id * 2, l, mid, pos, val, val1);
        ud(id * 2 + 1, mid + 1, r, pos, val, val1);
        bit[id] = bit[id * 2] + bit[id * 2 + 1];
    }
    void ud(int pos, int val, int val1){
        ud(1, 1, si, pos, val, val1);
    }
} stree[NN];
 
void dfs(int u, int p){
    siz[u] = 1;
    par[u] = p;
    dep[u] = dep[p] + 1;
    for (auto x : adj[u]){
        if (x == p) continue;
        dfs(x, u);
        siz[u] += siz[x];
    }
}

void init(int u, int top){
    hed[u] = top;
    id[u] = ++cnt;
    int hv = -1;
    for (auto x : adj[u]){
        if (x == par[u]) continue;
        if (hv == -1 || siz[u] > siz[hv]) hv = x;
    }
    if (hv != -1) init(hv, top);
    else stree[top].init(cnt);
    for (auto x : adj[u]){
        if (x == par[u] || x == hv) continue;
        cnt = 0;
        init(x, x);
    }
}

ii gt(int u){
    int a = min(stree[hed[u]].bit[1].a[0][0], stree[hed[u]].bit[1].a[0][1]);
    int b = min(stree[hed[u]].bit[1].a[1][1], stree[hed[u]].bit[1].a[1][0]);
    return {min(a, b + 1), min(a + 1, b)};
}

void ud(int u, int val1, int val2){
    if (u == 0) return;
    ii a = gt(u);
    stree[hed[u]].ud(id[u], val1, val2);
    
    ii b = gt(u);
    ud(par[hed[u]], b.fi - a.fi, b.se - a.se);
}

int res(){
    return min({stree[1].bit[1].a[0][0], stree[1].bit[1].a[0][1], stree[1].bit[1].a[1][0], stree[1].bit[1].a[1][1]});
}

int cat(int u){
    st[u] = 1;
    ud(u, 0, oo);
    return res();
}

int dog(int u){
    st[u] = 2;
    ud(u, oo, 0);
    return res();
}

int neighbor(int u){
    if (st[u] == 0) return res();
    if (st[u] == 1){
        ud(u, 0, -oo);
        st[u] = 0;
        return res();
    }
    ud(u, -oo, 0);
    st[u] = 0;
    return res();
}

void initialize(int N, vector<int> A, vector<int> B){
    n = N;
    for (int i = 0; i < n - 1; i++){
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }
    dfs(1, 0);
    init(1, 1);
}

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