Submission #1122809

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122809		FucKanh	Cats or Dogs (JOI18_catdog)	C++20	0 / 100	4 ms	5700 KiB

catdog

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 2;
const int inf = 1e7;

int n,state[maxn],sz[maxn],par[maxn];
int root[maxn], pos[maxn],cnt[maxn];
int dp[maxn][3];
int sumC[maxn], sumD[maxn];
vector<int> a[maxn];

void dfs(int u, int pa = -1) {
    sz[u] = 1;
    for (int i = 0; i < a[u].size(); i++) {
        int v = a[u][i];
        if (pa == v) continue;
        par[v] = u;
        dfs(v,u);
        sz[u] += sz[v];
        if (sz[v] >= sz[a[u][0]] || a[u][0] == pa) swap(a[u][0], a[u][i]);
    }
}

void hld(int u, int pa = -1) {
    if (a[u][0] == pa) return;
    root[a[u][0]] = root[u];
    pos[a[u][0]] = pos[u] + 1;
    hld(a[u][0], u);
    cnt[root[u]]++;

    for (int i = 1; i < a[u].size(); i++) {
        int v = a[u][i];
        if (pa == v) continue;

        root[a[u][i]] = a[u][i];
        pos[a[u][i]] = 1;
        cnt[a[u][i]] = 1;
        hld(a[u][i], u);
    }
}

class IT {
vector<array<int,4>> t;
int n;
public:
    void build(int v, int l, int r) {
        if (l==r) {
            t[v][0] = inf;
            t[v][1] = inf;
            t[v][2] = t[v][3] = 0;
            return;
        }
        int mid = l + r >> 1;
        build(v*2,l,mid);
        build(v*2+1,mid+1,r);
        t[v] = merged(t[v*2],t[v*2+1]);
    }
    void init(int N) {
        n = N;
        t.resize((n+1)*4,array<int,4>());
        build(1,1,n);
    }
    /*
        re[0] = cd
        re[1] = dc
        re[2] = cc
        re[3] = dd
    */
    array<int,4> merged(array<int,4> a, array<int,4> b) {
        array<int,4> re;
        if (b[0]==-inf) return a;
        if (a[0]==-inf) return b;
        re[0] = min({a[2] + b[0], a[0] + b[3], a[0] + b[0] + 1, a[2] + b[3] + 1});
        re[1] = min({a[3] + b[1], a[1] + b[2], a[3] + b[2] + 1, a[1] + b[1] + 1});
        re[2] = min({a[2] + b[2], a[0] + b[1], a[2] + b[1] + 1, a[0] + b[2] + 1});
        re[3] = min({a[3] + b[3], a[1] + b[0], a[3] + b[0] + 1, a[1] + b[3] + 1});
        return re;
    }
    void update(int v, int l, int r,int pos, int d, int c) {
        if (l==r) {
            t[v][0] = t[v][1] = inf;
            t[v][2] = c;
            t[v][3] = d;
//            cerr << "update node: " << v << " " << l << " " << r << " : " << t[v][0] << " " << t[v][1] << " " << t[v][2] << " " << t[v][3] << endl;
            return;
        }
        int mid = l + r >> 1;
        if (pos <= mid) update(v*2,l,mid,pos,d,c);
        else update(v*2+1,mid+1,r,pos,d,c);
        t[v] = merged(t[v*2],t[v*2+1]);
//        cerr << "update: " << v << " " << l << " " << r << " : " << t[v][0] << " " << t[v][1] << " " << t[v][2] << " " << t[v][3] << endl;
//        cerr << "FROM: " << t[v*2][0] << " " << t[v*2][1] << " " << t[v*2][2] << " " << t[v*2][3] << endl;
//        cerr << "FROM: " << t[v*2+1][0] << " " << t[v*2+1][1] << " " << t[v*2+1][2] << " " << t[v*2+1][3] << endl;
    }
    array<int,4> get(int v, int l, int r, int L, int R) {
        if (L > R) return array<int,4>({-inf,-inf,-inf,-inf});
        if (L == l && R == r) return t[v];
        int mid = l + r >> 1;
        return merged(get(v*2,l,mid,L,min(R,mid)), get(v*2+1,mid+1,r,max(mid+1,L),R));
    }
};

IT tree[maxn];

void initialize(int N, vector<int> A, vector<int> B) {
    n = N;
    for (int i = 0; i < N-1; i++) {
        a[A[i]].push_back(B[i]);
        a[B[i]].push_back(A[i]);
    }
    root[1] = 1;
    cnt[1] = 1;
    pos[1] = 1;
    dfs(1);
    hld(1);
    for (int i = 1; i <= n; i++) {
        if (root[i] == i) tree[i].init(cnt[i]);
    }
}

void query(int v) {
    array<int,4> pre,now;
    while (v) {
//        cerr << v << " - " << root[v] << " " << pos[v] << endl;
        pre = tree[root[v]].get(1,1,cnt[root[v]],1,cnt[root[v]]);

        if (state[v] == 1) tree[root[v]].update(1,1,cnt[root[v]],pos[v],inf,0);
        else if (state[v] == 2) tree[root[v]].update(1,1,cnt[root[v]],pos[v],0,inf);
        else tree[root[v]].update(1,1,cnt[root[v]],pos[v],sumD[v],sumC[v]);

//        cerr << "nxt " << root[v] << endl;

        now = tree[root[v]].get(1,1,cnt[root[v]],1,cnt[root[v]]);

        v = root[v];

        if (par[v] == 0) {
//            cerr << "Done" << endl;
            return;
        }
//        cerr << "Change sum: " << par[v] << " : " << min({now[1], pre[2], now[0] + 1, now[3] + 1}) - min({pre[1], pre[2],pre[0] + 1, pre[3] + 1}) << " " <<
//        min({now[1] + 1, pre[2] + 1, now[0], now[3]}) - min({pre[1] + 1, pre[2] + 1,pre[0], pre[3]}) << endl;
        sumC[par[v]] += min({now[1], pre[2], now[0] + 1, now[3] + 1}) - min({pre[1], pre[2],pre[0] + 1, pre[3] + 1});
        sumD[par[v]] += min({now[1] + 1, pre[2] + 1, now[0], now[3]}) - min({pre[1] + 1, pre[2] + 1,pre[0], pre[3]});

        v = par[v];
    }
}

int cat(int v) {
    state[v] = 1;
    query(v);
    array<int,4> tmp = tree[1].get(1,1,cnt[1],1,cnt[1]);
    int D = min({tmp[0], tmp[3], tmp[2] + 1, tmp[1] + 1});
    int C = min({tmp[0] + 1, tmp[3] + 1, tmp[2], tmp[1]});
    return min(D,C);
}

int dog(int v) {
    state[v] = 2;
    query(v);
    array<int,4> tmp = tree[1].get(1,1,cnt[1],1,cnt[1]);
    int D = min({tmp[0], tmp[3], tmp[2] + 1, tmp[1] + 1});
    int C = min({tmp[0] + 1, tmp[3] + 1, tmp[2], tmp[1]});
    return min(D,C);
}

int neighbor(int v) {
    state[v] = 0;
    query(v);
    array<int,4> tmp = tree[1].get(1,1,cnt[1],1,cnt[1]);
    int D = min({tmp[0], tmp[3], tmp[2] + 1, tmp[1] + 1});
    int C = min({tmp[0] + 1, tmp[3] + 1, tmp[2], tmp[1]});
    return min(D,C);
}
//
//signed main() {
//    initialize(5,vector<int>({1,2,2,4}), vector<int>({2,3,4,5}));
//    cout << cat(3) << endl;
//    cout << dog(5) << endl;
//    cout << cat(2) << endl;
//    cout << dog(1) << endl;
//    cout << neighbor(2) << endl;
//}

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