Submission #1123346

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123346		kiethm07	Cats or Dogs (JOI18_catdog)	C++20	100 / 100	164 ms	34632 KiB

catdog

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;
const int inf = 1e7;

vector<int> a[N];
int pa[N], sz[N], heavy[N];
int head[N], tin[N], curTime;
int SC[N], SD[N];
int id[N], chainSz[N], chainCnt;
int n;
int type[N];

struct node{
    int val[2][2];
    node(){
        val[0][0] = val[0][1] = val[1][0] = val[1][1] = inf;
    }
};

node combine(node& a,node& b){
    node n;
    for (int x = 0; x < 2; x++){
        for (int y = 0; y < 2; y++){
            for (int i = 0; i < 2; i++){
                for (int j = 0; j < 2; j++){
                    n.val[x][y] = min(n.val[x][y], a.val[x][i] + b.val[j][y] + (i != j));
                }
            }
        }
    }
    return n;
}

class IT{
private:
    vector<node> t;
    int n;
public:
    void init(int m){
        n = m;
        t.resize(n * 4);
    }
    void build(int id,int l,int r){
        if (l == r){
            t[id].val[0][0] = 0;
            t[id].val[1][1] = 0;
            t[id].val[0][1] = t[id].val[1][0] = inf;
            return;
        }
        int mid = (l + r) / 2;
        build(id * 2,l,mid);
        build(id * 2 + 1,mid + 1,r);
        t[id] = combine(t[id * 2],t[id * 2 + 1]);
    }
    void build(){
        build(1,1,n);
    }
    void update(int id,int l,int r,int i,int cat,int dog){
        if (l > i || r < i) return;
        if (l == r){
            t[id].val[0][0] = cat;
            t[id].val[1][1] = dog;
            t[id].val[0][1] = t[id].val[1][0] = inf;
            return;
        }
        int mid = (l + r) / 2;
        update(id * 2,l,mid,i,cat,dog);
        update(id * 2 + 1,mid + 1,r,i,cat,dog);
        t[id] = combine(t[id * 2],t[id * 2 + 1]);
    }
    void update(int i,int cat,int dog){
        update(1,1,n,i,cat,dog);
    }
    node getNode(){
        return t[1];
    }
};

IT t[N];

void dfs(int u,int p){
    sz[u] = 1;
    for (int v : a[u]){
        if (v == p) continue;
        pa[v] = u;
        dfs(v,u);
        if (sz[v] > sz[heavy[u]]) heavy[u] = v;
        sz[u] += sz[v];
    }
}

void hld(int u,int p){
    if (head[u] == 0){
        head[u] = u;
        id[u] = ++chainCnt;
    }
    chainSz[id[u]]++;
    tin[u] = ++curTime;
    int nxt = heavy[u];
    if (nxt == 0) return;
    head[nxt] = head[u];
    id[nxt] = chainCnt;
    hld(nxt,u);
    for (int v : a[u]){
        if (v == p || v == nxt) continue;
        hld(v,u);
    }
}

void initialize(int _N, vector<int> _A, vector<int> _B){
    n = _N;
    for (int i = 0; i < n - 1; i++){
        int u = _A[i];
        int v = _B[i];
        a[u].push_back(v);
        a[v].push_back(u);
    }
    dfs(1,-1);
    hld(1,-1);
//    for (int i = 1; i <= n; i++){
//        cout << i << " " << id[i] << "\n";
//    }
    for (int i = 1; i <= chainCnt; i++){
        t[i].init(chainSz[i]);
        t[i].build();
    }
}

void update(int u,int cat,int dog){
    while(u != 0){
        node f = t[id[u]].getNode();
        int preSC = min({f.val[0][0],f.val[0][1],f.val[1][0] + 1,f.val[1][1] + 1});
        int preSD = min({f.val[0][0] + 1,f.val[0][1] + 1,f.val[1][0],f.val[1][1]});
        SC[pa[head[u]]] -= preSC;
        SD[pa[head[u]]] -= preSD;
        t[id[u]].update(tin[u] - tin[head[u]] + 1,cat,dog);
//        cout << tin[u] - tin[head[u]] + 1 << " " << cat << " " << dog << '\n';
        node g = t[id[u]].getNode();
//        cout << "g: " << g.val[0][0] << " " << g.val[1][1] << " " << g.val[0][1] << " " << g.val[1][0] << '\n';
        SC[pa[head[u]]] += min({g.val[0][0],g.val[0][1],g.val[1][0] + 1,g.val[1][1] + 1});
        SD[pa[head[u]]] += min({g.val[0][0] + 1,g.val[0][1] + 1,g.val[1][0],g.val[1][1]});
//        cout << SC[pa[head[u]]] << " " << SD[pa[head[u]]] << "\n";
        u = pa[head[u]];
        cat = type[u] != 2 ? SC[u] : inf;
        dog = type[u] != 1 ? SD[u] : inf;
    }
}

int cat(int u){
    type[u] = 1;
    update(u,SC[u],inf);
    node f = t[id[1]].getNode();
    return min({f.val[0][0],f.val[0][1],f.val[1][0],f.val[1][1]});
}

int dog(int u){
    type[u] = 2;
    update(u,inf,SD[u]);
    node f = t[id[1]].getNode();
    return min({f.val[0][0],f.val[0][1],f.val[1][0],f.val[1][1]});
}

int neighbor(int u){
    type[u] = 0;
    update(u,SC[u],SD[u]);
    node f = t[id[1]].getNode();
    return min({f.val[0][0],f.val[0][1],f.val[1][0],f.val[1][1]});
}

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