Submission #1282868

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282868		baotoan655	Cats or Dogs (JOI18_catdog)	C++20	100 / 100	130 ms	36256 KiB

catdog

#include <bits/stdc++.h>
#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;

const int inf = 1e6;
const int N = 1e5 + 5;
struct node {
    int dp[2][2];
    node(int a = inf, int b = inf, int c = inf, int d = inf) {
        dp[0][0] = a;
        dp[0][1] = b;
        dp[1][0] = c;
        dp[1][1] = d;
    }
    node operator + (const node& o) const {
        node res;
        for(int i = 0; i < 2; ++i) {
            for(int j = 0; j < 2; ++j) {
                for(int k = 0; k < 2; ++k) {
                    for(int l = 0; l < 2; ++l) {
                        res.dp[i][j] = min(res.dp[i][j], dp[i][k] + o.dp[l][j] + (k != l));
                    }
                }
            }
        }
        return res;
    }
    int ans() {
        return min({dp[0][0], dp[0][1], dp[1][0], dp[1][1]});
    }
};
node base[] = {
    node(0, inf, inf, 0),
    node(0, inf, inf, inf),
    node(inf, inf, inf, 0)
};
struct SEG {
    vector<node> it;
    int n;
    SEG(int _n = 0) {
        n = _n;
        it.assign(4 * n + 5, node());
    }
    void build(int k, int l, int r) {
        if(l == r) {
            it[k] = base[0];
            return;
        }
        int mid = l + r >> 1;
        build(k << 1, l, mid);
        build(k << 1 | 1, mid + 1, r);
        it[k] = it[k << 1] + it[k << 1 | 1];
    }
    void update(int pos, node val) {
        int l = 1, r = n, k = 1;
        while(l < r) {
            int mid = l + r >> 1;
            if(pos <= mid) {
                k = (k << 1);
                r = mid;
            } else {
                k = (k << 1 | 1);
                l = mid + 1;
            }
        }
        it[k] = val;
        while(k) {
            k >>= 1;
            it[k] = it[k << 1] + it[k << 1 | 1];
        }
    }
};

int n;
vector<int> g[N];
int id[N], curId, pos[N], len[N], top[N], fa[N], sz[N];
int type[N];
int sumChild[2][N];
SEG tree[N];
void dfs(int u, int p) {
    sz[u] = 1;
    for(int v : g[u]) if(v != p) {
            fa[v] = u;
            dfs(v, u);
            sz[u] += sz[v];
        }
}
void hld(int u, int p) {
    if(!id[u]) {
        id[u] = ++curId;
        top[curId] = u;
    }
    pos[u] = ++len[curId];
    int hc = -1;
    for(int v : g[u]) if(v != p) {
            if(hc == -1 || sz[v] > sz[hc]) hc = v;
        }
    if(hc != -1) {
        id[hc] = id[u];
        hld(hc, u);
    }
    for(int v : g[u]) if(v != p && v != hc) {
            hld(v, u);
        }
}
void initialize(int _n, vector<int> A, vector<int> B) {
    n = _n;
    for(int i = 0; i < n - 1; ++i) {
        g[A[i]].emplace_back(B[i]);
        g[B[i]].emplace_back(A[i]);
    }
    dfs(1, 0);
    hld(1, 0);
    for(int i = 1; i <= n; ++i) {
        if(i == top[id[i]]) {
            tree[i] = SEG(len[id[i]]);
            tree[i].build(1, 1, len[id[i]]);
        }
    }
}
void upd(int u) {
    while(u > 0) {
        int head = top[id[u]];
        node c = tree[head].it[1];
        int p = fa[head];
        sumChild[0][p] -= min({c.dp[0][0], c.dp[0][1], c.dp[1][0] + 1, c.dp[1][1] + 1});
        sumChild[1][p] -= min({c.dp[1][0], c.dp[1][1], c.dp[0][0] + 1, c.dp[0][1] + 1});
        c = base[type[u]];
        if(c.dp[0][0] != inf) c.dp[0][0] += sumChild[0][u];
        if(c.dp[1][1] != inf) c.dp[1][1] += sumChild[1][u];
        tree[head].update(pos[u], c);

        c = tree[head].it[1];
        sumChild[0][p] += min({c.dp[0][0], c.dp[0][1], c.dp[1][0] + 1, c.dp[1][1] + 1});
        sumChild[1][p] += min({c.dp[1][0], c.dp[1][1], c.dp[0][0] + 1, c.dp[0][1] + 1});
        u = p;
    }

}
int cat(int x) {
    type[x] = 1;
    upd(x);
    return tree[1].it[1].ans();
}
int dog(int x) {
    type[x] = 2;
    upd(x);
    return tree[1].it[1].ans();
}
int neighbor(int x) {
    type[x] = 0;
    upd(x);
    return tree[1].it[1].ans();
}

//int32_t main() {
//    ios_base::sync_with_stdio(false);
//    cin.tie(0), cout.tie(0);
//
//    file("A") else file("task");
//    int _n, _q;
//    cin >> _n;
//    vector<int> A(_n - 1), B(_n - 1);
//    for(int i = 0; i < _n - 1; ++i) cin >> A[i] >> B[i];
//    initialize(_n, A, B);
//
//    cin >> _q;
//    while(_q--) {
//        int t, x;
//        cin >> t >> x;
//        if(t == 1) cout << cat(x) << '\n';
//        if(t == 2) cout << dog(x) << '\n';
//        if(t == 3) cout << neighbor(x) << '\n';
//    }
//    return 0;
//}

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