Submission #1119387

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119387		Requiem	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	2451 ms	80640 KiB

catdog

#include "catdog.h"
#include<bits/stdc++.h>
//#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e9
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "catdogs"
using namespace std;
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
/**
Cat / Dogs:

Cho 1 cây n đỉnh với n - 1 cạnh.

Một số đỉnh có màu đỏ / xanh.

Tìm tập cạnh tối thiểu sao cho:
==> trên đường đi giữa 1 cặp đỉnh xanh / đỏ bất kì đều tồn tại 1 cạnh trong tập đã chọn

subtask 2: N <= 1000, Q <= 1000.
O(N * Q).
Ta dựng cây lên.
Với 1 subtree của thằng u, ta nhận coi là nó là thằng blue / red.

Nếu số thằng blue > red thì mình cho blue lên, và chặn hết đống red.
**/
/**
bài này thực ra là kĩ thuật dynamic DP trên HLD.
Với đỉnh u, ta gọi dp[2][2]:

fout[0]: tổng các thằng nhỏ nhất không nằm trên cùng chain với u.
nếu như ta chọn theo màu i

fout[1]: tổng các thằng lớn nhất nằm trong cùng chain với u.

f[0] = fout[0] + min(f[nxtOnChain][1] + 1, f[nxtOnChain][0]);
f[1] = fout[1] + min(f[nxtOnChain][0] + 1, f[nxtOnChain][1]);
Bài này ta sẽ cố dùng nhân ma trận để tối ưu tính trạng thái.

Bây giờ cập nhật như thế nào đây.

Bắt đầu ở đỉnh u,
Nếu biến nó thành đỉnh loại 0 / 1:

Mình sẽ phế cái hàng 0 / 1 của ma trận chuyển trạng thái

Lúc này mình cần phải tính lại cái ma trận chuyển trạng thái

Kết quả của ta sẽ không thay đổi
khi mình gắn thêm 1 nút vô hình ở dưới vào, cái hàm của thằng đó là [0, 0].

Mình sẽ skip hết tất cả các nút ở giữa chain bởi vì mình có thể dùng ma trận chuyển trạng thái
để tính nhanh các thằng đó.

Giả sử mình đang ở đỉnh chain, nút p.
**/

int complexity = 0;
struct matrix{
    vector<vector<int>> mat;
    int r = 0, c = 0;
    matrix(int _r = 0, int _c = 0){
        r = _r;
        c = _c;
        mat.resize(r + 1, vector<int>(c + 1, 0));
    }

    matrix operator * (const matrix &other){
        matrix res(r, other.c);

        FOR(i, 0, r - 1){
            FOR(j, 0, other.c - 1){
                res.mat[i][j] = inf;
                FOR(k, 0, c - 1){
                    complexity++;
                    res.mat[i][j] = min(res.mat[i][j], mat[i][k] + other.mat[k][j]);
                }
            }
        }
        return res;
    }

    void print(){
        FOR(i, 0, r - 1){
            FOR(j, 0, c - 1){
                cout << mat[i][j] << ' ';
            }
            cout << endl;

        }
    }

};

const int MAXN = 1e5 + 9;
int n;
ii edge[MAXN];
vector<int> g[MAXN];
bool catNode[MAXN], dogNode[MAXN];

int sz[MAXN], depth[MAXN], par[MAXN];

int headChain[MAXN], idChain[MAXN], in[MAXN], endChain[MAXN];
int f[MAXN][2], fout[MAXN][2], numChain;

vector<int> etour;
struct segtree{
    int sz =0 ;
    vector<matrix> st;
    segtree(int _sz = 0){
        sz = _sz;
        st.resize(sz * 4 + 9);
    }

    void mergeNode(matrix &node, matrix &lnode, matrix rnode){
        FOR(i, 0, lnode.r - 1){
            FOR(j, 0, rnode.c - 1){
                node.mat[i][j] = inf;
                FOR(k, 0, lnode.c - 1){
                    minimize(node.mat[i][j], lnode.mat[i][k] + rnode.mat[k][j]);
                }
            }
        }
    }

    void build(int nn, int l, int r){
        if (l == r){
            st[nn] = matrix(2, 2);
            st[nn].mat[0][1] = st[nn].mat[1][0] = 1;
            return;
        }
        int mid = (l + r) >> 1;
        build(nn << 1, l, mid);
        build(nn << 1 | 1, mid + 1, r);
        st[nn] = matrix(2, 2);
        mergeNode(st[nn], st[nn << 1], st[nn << 1 | 1]);
    }

    void changePos(int nn, int l, int r, int pos, matrix &newMat){
        if (l == r){
            st[nn] = newMat;
            return;
        }

        int mid = (l + r) >> 1;
        if (pos <= mid) changePos(nn << 1, l, mid, pos, newMat);
        else changePos(nn << 1 | 1, mid + 1, r, pos, newMat);

        mergeNode(st[nn], st[nn << 1], st[nn << 1 | 1]);
    }

    void getRange(int nn, int l, int r, int u, int v, matrix &res){
        if (l >= u and r <= v){
            if (res.mat[0][0] == -1) res = st[nn];
            else res = res * st[nn];
            return;
        }
        if (l > v or r < u) return;
        int mid = (l + r) >> 1;
        getRange(nn << 1, l, mid, u, v, res);
        getRange(nn << 1 | 1, mid + 1, r, u, v, res);
    }

    void changePos(int pos, matrix newMat){
        changePos(1, 0, sz, pos, newMat);
    }
    matrix getRange(int u, int v){
        matrix res = matrix(2, 2);
        res.mat[0][0] = -1;
        getRange(1, 0, sz, u, v, res);
        return res;
    }
} opt;

void precalc(int u,int p){
    sz[u] = 1;
    par[u] = p;
    for(auto id: g[u]){
        int v = edge[id].se + edge[id].fi - u;
        if (v == p) continue;
        depth[v] = depth[u] + 1;
        precalc(v, u);
        sz[u] += sz[v];
    }
}

void buildHLD(int u, int p){
    int bigchild = -1;
    in[u] = etour.size();
    endChain[numChain] = in[u];
    etour.pb(u);

    idChain[u] = numChain;

    for(auto id: g[u]){
        int v = edge[id].se + edge[id].fi - u;
        if (v == p) continue;

        if (bigchild == -1 or sz[bigchild] < sz[v]) bigchild = v;
    }
    if (bigchild != -1) buildHLD(bigchild, u);

    for(auto id: g[u]){
        int v = edge[id].se + edge[id].fi - u;
        if (v == p or v == bigchild) continue;
        ++numChain;
        headChain[numChain] = v;
        buildHLD(v, u);
    }


}

void modifyNode(int u){
    matrix newMat(2, 2);
    if (dogNode[u]){
        newMat.mat[0][0] = newMat.mat[0][1] = inf;
        newMat.mat[1][0] = fout[u][1] + 1;
        newMat.mat[1][1] = fout[u][1];
    }
    else if (catNode[u]){
        newMat.mat[0][0] = fout[u][0];
        newMat.mat[0][1] = fout[u][0] + 1;
        newMat.mat[1][0] = newMat.mat[1][1] = inf;
    }
    else{
        newMat.mat[0][0] = fout[u][0];
        newMat.mat[0][1] = fout[u][0] + 1;
        newMat.mat[1][0] = fout[u][1] + 1;
        newMat.mat[1][1] = fout[u][1];
    }
//    cout << "UPDATE NODE: " << u << endl;
//    newMat.print();
    opt.changePos(in[u], newMat);
}

void updatePath(int u){

    while(true){
        modifyNode(u);

        int p = headChain[idChain[u]];
        int nxtP = par[p];

        matrix curF = matrix(2, 1);
        curF = opt.getRange(in[p], endChain[idChain[u]]) * curF;

        if (nxtP != -1) fout[nxtP][0] -= min(f[p][0], f[p][1] + 1);
        if (nxtP != -1) fout[nxtP][1] -= min(f[p][1], f[p][0] + 1);

        f[p][0] = curF.mat[0][0];
        f[p][1] = curF.mat[1][0];
//        cout << "ON PATH: " << p << ' ' << f[p][0] << ' ' << f[p][1] << endl;

        if (nxtP != -1) fout[nxtP][0] += min(f[p][0], f[p][1] + 1);
        if (nxtP != -1) fout[nxtP][1] += min(f[p][1], f[p][0] + 1);

        u = nxtP;

        if (u == -1) return;
    }
}

int getAns(){
    return min(f[1][0], f[1][1]);
}

void initialize(int N, vector<int> A, vector<int> B){
    n = N;
    memset(catNode, false, sizeof(catNode));
    memset(dogNode, false, sizeof(dogNode));
    FOR(i, 0, n - 2){
        edge[i] = {A[i], B[i]};
        g[A[i]].pb(i);
        g[B[i]].pb(i);
    }
    headChain[0] = 1;
    numChain = 0;
    precalc(1, -1);
    buildHLD(1, -1);

    opt =segtree(n);
    opt.build(1, 0, opt.sz);
}

int cat(int u){
    catNode[u] = true;
    updatePath(u);
    return getAns();
}

int dog(int u){
    dogNode[u] = true;
    updatePath(u);
    return getAns();
}

int neighbor(int u){
    catNode[u] = dogNode[u] = false;
    updatePath(u);
    return getAns();
}

/**
Warning:
Đọc sai đề???
Cận lmao
Code imple thiếu case nào không.
Limit.
**/

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