Submission #1122829

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122829		FucKanh	Cats or Dogs (JOI18_catdog)	C++20	100 / 100	128 ms	26948 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;
            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+1],t[v*2]);
    }
    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+1,mid+1,r,max(mid+1,L),R),get(v*2,l,mid,L,min(R,mid)));
    }
};

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) {
        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,sumC[v]);
        else if (state[v] == 2) tree[root[v]].update(1,1,cnt[root[v]],pos[v],sumD[v],inf);
        else tree[root[v]].update(1,1,cnt[root[v]],pos[v],sumD[v],sumC[v]);


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

        v = root[v];

        if (par[v] == 0) {
            return;
        }
        sumC[par[v]] += min({now[1], now[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, now[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);
}
//void file(string name) {
//    if (fopen((name + ".inp").c_str(), "r")) {
//        freopen((name + ".inp").c_str(), "r", stdin);
//        freopen((name + ".out").c_str(), "w", stdout);
//    }
//}
//signed main() {
//    file("DOGCAT");
//    int n; cin >> n;
//    vector<int> A,B;
//    for (int i = 1; i < n; i++) {
//        int x,y; cin >> x >> y;
//        A.push_back(x);
//        B.push_back(y);
//    }
//    initialize(n,A,B);
//    int q; cin >> q;
//    for (int i = 1; i <= q; i++) {
//        int t,x; cin >> t >> x;
//        if (t==1) cout << cat(x) << endl;
//        else if (t==2) cout << dog(x) << endl;
//        else cout << neighbor(x) << endl;
//    }
//}

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