Submission #374891

#	Time	Username	Problem	Language	Result	Execution time	Memory
374891		valerikk	Cats or Dogs (JOI18_catdog)	C++17	0 / 100	6 ms	8940 KiB

catdog

#include <bits/stdc++.h>

using namespace std;

const int INF = (int)1e9;

struct Data {
    int dp[2][2];

    Data() {
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) dp[i][j] = INF;
        }
    }

    Data(int sum1, int sum2, int type) {
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {
                dp[i][j] = INF;
            }
        }
        if (type != 2) dp[0][0] = sum1;
        if (type != 1) dp[1][1] = sum2;
    }
};
Data merge(const Data& l, const Data& r) {
    Data res = Data{};
    for (int pl = 0; pl < 2; ++pl) {
        for (int ql = 0; ql < 2; ++ql) {
            if (l.dp[pl][ql] == INF) continue;
            for (int pr = 0; pr < 2; ++pr) {
                for (int qr = 0; qr < 2; ++qr) {
                    if (r.dp[pr][qr] == INF) continue;
                    int cur = l.dp[pl][ql] + r.dp[pr][qr];
                    if (ql != pr) ++cur;
                    res.dp[pl][qr] = min(res.dp[pl][qr], cur);
                }
            }
        }
    }
    return res;
}

const int N = (int)1e5 + 7;

Data t[4 * N];

void upd(int v, int vl, int vr, int pos, int sum1, int sum2, int type) {
    if (vr - vl == 1) {
        t[v] = Data{sum1, sum2, type};
    } else {
        int vm = (vl + vr) / 2;
        if (pos < vm) {
            upd(2 * v, vl, vm, pos, sum1, sum2, type);
        } else {
            upd(2 * v + 1, vm, vr, pos, sum1, sum2, type);
        }
        t[v] = merge(t[2 * v], t[2 * v + 1]);
    }
}

Data query(int v, int vl, int vr, int l, int r) {
    if (vl >= l && vr <= r) return t[v];
    int vm = (vl + vr) / 2;
    if (r <= vm) return query(2 * v, vl, vm, l, r);
    if (vm <= l) return query(2 * v + 1, vm, vr, l, r);
    return merge(query(2 * v, vl, vm, l, r), query(2 * v + 1, vm, vr, l, r));
}

void tbuild(int v, int vl, int vr) {
    if (vr - vl == 1) {
        t[v] = Data{0, 0, 0};
    } else {
        int vm = (vl + vr) / 2;
        tbuild(2 * v, vl, vm);
        tbuild(2 * v + 1, vm, vr);
        t[v] = merge(t[2 * v], t[2 * v + 1]);
    }
}

int n;
vector<int> g[N];
int a[N], b[N];
int sz[N];
int head[N];
int in[N]/*, out[N]*/, T = 0;
int cnt[N];
int type[N], sum1[N], sum2[N];
int par[N];

int find_size(int v, int p = -1) {
    par[v] = p;
    sz[v] = 1;
    vector<int> gg;
    for (int u : g[v]) {
        if (u != p) {
            sz[v] += find_size(u, v);
            gg.push_back(u);
        }
    }
    g[v] = gg;
    return sz[v];
}

void build_hld(int v) {
    for (int& u : g[v]) {
        if (sz[u] > sz[g[v][0]]) swap(u, g[v][0]);
    }
    ++cnt[head[v]];
    in[v] = T++;
    for (int u : g[v]) {
        head[u] = u == g[v][0] ? head[v] : u;
        build_hld(u);
    }
    //out[v] = T;
}

Data get_dp(int v) {
    return query(1, 0, n, in[head[v]] - cnt[head[v]] + 1, in[v] + 1);
}

void change(int v, int s1, int s2, int type1) {
    upd(1, 0, n, in[v], s1, s2, type1);
}

void init() {
    find_size(0);
    head[0] = 0;
    for (int i = 0; i < n; ++i) cnt[i] = 0;
    build_hld(0);
    tbuild(1, 0, n);
    for (int i = 0; i < n; ++i) {
        type[i] = sum1[i] = sum2[i] = 0;
    }
}

int get_ans() {
    auto res1 = get_dp(0);
    int res = INF;
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) res = min(res, res1.dp[i][j]);
    }
    return res;
}

void change_type(int V, int ntype) {
    int v = V;
    while (v != -1) {
        if (v == head[v]) {
            if (par[v] == -1) break;
            auto cur = get_dp(v);
            int dp1 = min(cur.dp[0][0], cur.dp[1][0]);
            int dp2 = min(cur.dp[0][1], cur.dp[1][1]);
            sum1[par[v]] -= min(dp1, dp2 + 1);
            sum2[par[v]] -= min(dp2, dp1 + 1);
            v = par[v];
        } else {
            v = head[v];
        }
    }
    type[V] = ntype;
    v = V;
    while (v != -1) {
        change(v, sum1[v], sum2[v], type[v]);
        if (v == head[v]) {
            if (par[v] == -1) break;
            auto cur = get_dp(v);
            int dp1 = min(cur.dp[0][0], cur.dp[1][0]);
            int dp2 = min(cur.dp[0][1], cur.dp[1][1]);
            sum1[par[v]] += min(dp1, dp2 + 1);
            sum2[par[v]] += min(dp2, dp1 + 1);
            v = par[v];
        } else {
            v = head[v];
        }
    }
}

void initialize(int initn, vector<int> inita, vector<int> initb) {
    n = initn;
    for (int i = 0; i < n - 1; ++i) {
        a[i] = inita[i] - 1;
        b[i] = initb[i] - 1;
        g[a[i]].push_back(b[i]);
        g[b[i]].push_back(a[i]);
    }
    init();
}

int cat(int v) {
    --v;
    change_type(v, 1);
    return get_ans();
}

int dog(int v) {
    --v;
    change_type(v, 2);
    return get_ans();
}

int neighbor(int v) {
    --v;
    change_type(v, 0);
    return get_ans();
}

#ifndef EVAL
int main() {
    freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int initn;
    cin >> initn;
    vector<int> inita(initn - 1), initb(initn - 1);
    for (int i = 0; i < initn - 1; ++i) {
        cin >> inita[i] >> initb[i];
    }
    initialize(initn, inita, initb);
    int qqq;
    cin >> qqq;
    while (qqq--) {
        int kektype, kekv;
        cin >> kektype >> kekv;
        if (kektype == 1) {
            cout << cat(kekv);
        }
        if (kektype == 2) {
            cout << dog(kekv);
        }
        if (kektype == 3) {
            cout << neighbor(kekv);
        }
        cout << '\n';
    }
    return 0;
}
#endif

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