Submission #345621

#	Time	Username	Problem	Language	Result	Execution time	Memory
345621		two_sides	Cats or Dogs (JOI18_catdog)	C++17	38 / 100	3070 ms	10844 KiB

catdog

#include <bits/stdc++.h>

using namespace std;

template <class X, class Y>
bool cmin(X &a, const Y &b) {
    return a > b ? a = b, 1 : 0;
}

const int INF = 1e9;

struct segTree {
    using Tp = array <array <int, 2>, 2>;

    vector <Tp> tr; int n, lo, hi; Tp res;

    Tp base() {
        Tp c; c[0][1] = c[1][0] = INF;
        c[0][0] = c[1][1] = 0; return c;
    }

    Tp comb(const Tp &a, const Tp &b) {
        if (a[0][0] < 0) return b; Tp c;
        c[0][1] = min({a[0][0] +
        b[0][1], a[0][0] + b[1][1]
        + 1, a[0][1] + b[1][1],
        a[0][1] + b[0][1] + 1, INF});
        c[1][0] = min({a[1][0] +
        b[0][0], a[1][0] + b[1][0]
        + 1, a[1][1] + b[1][0],
        a[1][1] + b[0][0] + 1, INF});
        c[0][0] = min({a[0][0] +
        b[0][0], a[0][0] + b[1][0]
        + 1, a[0][1] + b[1][0],
        a[0][1] + b[0][0] + 1, INF});
        c[1][1] = min({a[1][0] +
        b[0][1], a[1][0] + b[1][1]
        + 1, a[1][1] + b[1][1],
        a[1][1] + b[0][1] + 1, INF});
        return c;
    }

    void build(int i, int l, int r) {
        if (l == r) tr[i] = base();
        else {
            int m = (l + r) / 2;
            build(i * 2, l, m);
            build(i * 2 + 1, m + 1, r);
            tr[i][0][1] = min({INF,
            tr[i * 2][0][0] + tr[i * 2 + 1][0][1],
            tr[i * 2][0][0] + tr[i * 2 + 1][1][1] + 1,
            tr[i * 2][0][1] + tr[i * 2 + 1][1][1],
            tr[i * 2][0][1] + tr[i * 2 + 1][0][1] + 1});
            tr[i][1][0] = min({INF,
            tr[i * 2][1][0] + tr[i * 2 + 1][0][0],
            tr[i * 2][1][0] + tr[i * 2 + 1][1][0] + 1,
            tr[i * 2][1][1] + tr[i * 2 + 1][1][0],
            tr[i * 2][1][1] + tr[i * 2 + 1][0][0] + 1});
            tr[i][0][0] = min({INF, 
            tr[i * 2][0][0] + tr[i * 2 + 1][0][0],
            tr[i * 2][0][0] + tr[i * 2 + 1][1][0]
            + 1, tr[i * 2][0][1] + tr[i * 2 + 1][1][0],
            tr[i * 2][0][1] + tr[i * 2 + 1][0][0] + 1});
            tr[i][1][1] = min({INF,
            tr[i * 2][1][0] + tr[i * 2 + 1][0][1],
            tr[i * 2][1][0] + tr[i * 2 + 1][1][1] + 1,
            tr[i * 2][1][1] + tr[i * 2 + 1][1][1],
            tr[i * 2][1][1] + tr[i * 2 + 1][0][1] + 1,});
        }
    }

    void init(int n) {
        tr.resize((this->n = n) * 4);
        build(1, 1, n);
    }

    void update(int i, int l, int r, int t, int v) {
        if (l == r) return void(tr[i][t][t] = v);
        int m = (l + r) / 2;
        if (m >= lo) update(i * 2, l, m, t, v);
        else update(i * 2 + 1, m + 1, r, t, v);
        tr[i][0][1] = min({INF,
        tr[i * 2][0][0] + tr[i * 2 + 1][0][1],
        tr[i * 2][0][0] + tr[i * 2 + 1][1][1] + 1,
        tr[i * 2][0][1] + tr[i * 2 + 1][1][1],
        tr[i * 2][0][1] + tr[i * 2 + 1][0][1] + 1});
        tr[i][1][0] = min({INF,
        tr[i * 2][1][0] + tr[i * 2 + 1][0][0],
        tr[i * 2][1][0] + tr[i * 2 + 1][1][0] + 1,
        tr[i * 2][1][1] + tr[i * 2 + 1][1][0],
        tr[i * 2][1][1] + tr[i * 2 + 1][0][0] + 1});
        tr[i][0][0] = min({INF, 
        tr[i * 2][0][0] + tr[i * 2 + 1][0][0],
        tr[i * 2][0][0] + tr[i * 2 + 1][1][0]
        + 1, tr[i * 2][0][1] + tr[i * 2 + 1][1][0],
        tr[i * 2][0][1] + tr[i * 2 + 1][0][0] + 1});
        tr[i][1][1] = min({INF,
        tr[i * 2][1][0] + tr[i * 2 + 1][0][1],
        tr[i * 2][1][0] + tr[i * 2 + 1][1][1] + 1,
        tr[i * 2][1][1] + tr[i * 2 + 1][1][1],
        tr[i * 2][1][1] + tr[i * 2 + 1][0][1] + 1,});
    }

    void update(int p, int t, int v) {
        lo = p; update(1, 1, n, t, v);
    }

    void query(int i, int l, int r) {
        if (l >= lo && r <= hi) {
            if (res[0][0] < 0) res = tr[i];
            else {
                Tp tmp;
                tmp[0][1] = min({res[0][0] +
                tr[i][0][1], res[0][0] + tr[i][1][1]
                + 1, res[0][1] + tr[i][1][1],
                res[0][1] + tr[i][0][1] + 1, INF});
                tmp[1][0] = min({res[1][0] +
                tr[i][0][0], res[1][0] + tr[i][1][0]
                + 1, res[1][1] + tr[i][1][0],
                res[1][1] + tr[i][0][0] + 1, INF});
                tmp[0][0] = min({res[0][0] +
                tr[i][0][0], res[0][0] + tr[i][1][0]
                + 1, res[0][1] + tr[i][1][0],
                res[0][1] + tr[i][0][0] + 1, INF});
                tmp[1][1] = min({res[1][0] +
                tr[i][0][1], res[1][0] + tr[i][1][1]
                + 1, res[1][1] + tr[i][1][1],
                res[1][1] + tr[i][0][1] + 1, INF});
                res = tmp;
            }
            return;
        }
        int m = (l + r) / 2;
        if (m >= lo) query(i * 2, l, m);
        if (m < hi) query(i * 2 + 1, m + 1, r);
    }

    Tp query(int l, int r) {
        lo = l; hi = r; res[0][0] = -1;
        query(1, 1, n); return res;
    }
};

const int N = 100005;

vector <int> adj[N];
int f[N][2], g[N][2];
int hv[N], head[N], par[N], col[N];
int tin[N], tout[N], timer, en[N];
segTree ST;

int DFSpre(int u) {
    int sz = 1, big = 0, tmp;
    for (int v : adj[u]) {
        if (v == par[u]) continue;
        par[v] = u;
        sz += tmp = DFSpre(v);
        if (tmp > big) {
            tmp = big; hv[u] = v;
        }
    }
    return sz;
}

void DFSsplit(int u) {
    tin[u] = ++timer;
    if (par[u] && u == hv[par[u]])
        head[u] = head[par[u]];
    else head[u] = u;
    if (hv[u]) {
        DFSsplit(hv[u]); en[u] = en[hv[u]];
    }
    else en[u] = u;
    for (int v : adj[u])
        if (v != par[u] && v != hv[u])
            DFSsplit(v);
    tout[u] = timer;
}

void update(int u, int t) {
    if (t < 2) ST.update(tin[u], 1 - t, INF);
    else ST.update(tin[u], 1 - col[u], g[u][1 - col[u]]);
    col[u] = t;
    while (u) {
        u = head[u];
        if (par[u]) {
            g[par[u]][0] -= min(f[u][0], f[u][1] + 1);
            g[par[u]][1] -= min(f[u][0] + 1, f[u][1]);
        }
        auto res = ST.query(tin[u], tin[en[u]]);
        if (col[u] == 0 || col[u] == 2)
            f[u][0] = min(res[0][0], res[0][1]);
        else f[u][0] = INF;
        if (col[u] == 1 || col[u] == 2)
            f[u][1] = min(res[1][0], res[1][1]);
        else f[u][1] = INF;
        if (par[u]) {
            g[par[u]][0] += min(f[u][0], f[u][1] + 1);
            if (col[par[u]] == 0 || col[par[u]] == 2)
                ST.update(tin[par[u]], 0, g[par[u]][0]);
            g[par[u]][1] += min(f[u][0] + 1, f[u][1]);
            if (col[par[u]] == 1 || col[par[u]] == 2)
                ST.update(tin[par[u]], 1, g[par[u]][1]);
        }
        u = par[u];
    }
}

void initialize(int n, vector <int> a, vector <int> b) {
    fill(col + 1, col + n + 1, 2);
    for (int i = 0; i < n - 1; i++) {
        adj[a[i]].push_back(b[i]);
        adj[b[i]].push_back(a[i]);
    }
    DFSpre(1); DFSsplit(1); ST.init(n);
}

int cat(int u) {
    update(u, 0); return min(f[1][0], f[1][1]);
}

int dog(int u) {
    update(u, 1); return min(f[1][0], f[1][1]);
}

int neighbor(int u) {
    update(u, 2); return min(f[1][0], f[1][1]);
}

Compilation message (stderr)

catdog.cpp: In member function 'segTree::Tp segTree::comb(const Tp&, const Tp&)':
catdog.cpp:23:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   23 |         if (a[0][0] < 0) return b; Tp c;
      |         ^~
catdog.cpp:23:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   23 |         if (a[0][0] < 0) return b; Tp c;
      |                                    ^~

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