oj.uz

Submission #345616

# Submission time Handle Problem Language Result Execution time Memory
345616 2021-01-07T16:32:27 Z two_sides Cats or Dogs (JOI18_catdog) C++17
38 / 100
 3000 ms 11996 KB 
#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] = comb(tr[i * 2], tr[i * 2 + 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] = comb(tr[i * 2], tr[i * 2 + 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) {
            res = comb(res, tr[i]); 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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Correct 2 ms 2668 KB Output is correct
8 Correct 2 ms 2668 KB Output is correct
9 Correct 2 ms 2668 KB Output is correct
10 Correct 2 ms 2668 KB Output is correct
11 Correct 2 ms 2668 KB Output is correct
12 Correct 2 ms 2668 KB Output is correct
13 Correct 2 ms 2668 KB Output is correct
14 Correct 2 ms 2668 KB Output is correct
15 Correct 2 ms 2668 KB Output is correct
16 Correct 3 ms 2668 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Correct 2 ms 2668 KB Output is correct
8 Correct 2 ms 2668 KB Output is correct
9 Correct 2 ms 2668 KB Output is correct
10 Correct 2 ms 2668 KB Output is correct
11 Correct 2 ms 2668 KB Output is correct
12 Correct 2 ms 2668 KB Output is correct
13 Correct 2 ms 2668 KB Output is correct
14 Correct 2 ms 2668 KB Output is correct
15 Correct 2 ms 2668 KB Output is correct
16 Correct 3 ms 2668 KB Output is correct
17 Correct 10 ms 2796 KB Output is correct
18 Correct 10 ms 2796 KB Output is correct
19 Correct 8 ms 2796 KB Output is correct
20 Correct 2 ms 2796 KB Output is correct
21 Correct 4 ms 2796 KB Output is correct
22 Correct 5 ms 2796 KB Output is correct
23 Correct 12 ms 2796 KB Output is correct
24 Correct 14 ms 2796 KB Output is correct
25 Correct 7 ms 2796 KB Output is correct
26 Correct 5 ms 2796 KB Output is correct
27 Correct 3 ms 2796 KB Output is correct
28 Correct 3 ms 2924 KB Output is correct
29 Correct 5 ms 2924 KB Output is correct
30 Correct 3 ms 2796 KB Output is correct
31 Correct 3 ms 2796 KB Output is correct
32 Correct 3 ms 2796 KB Output is correct

Subtask #3
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Correct 2 ms 2668 KB Output is correct
8 Correct 2 ms 2668 KB Output is correct
9 Correct 2 ms 2668 KB Output is correct
10 Correct 2 ms 2668 KB Output is correct
11 Correct 2 ms 2668 KB Output is correct
12 Correct 2 ms 2668 KB Output is correct
13 Correct 2 ms 2668 KB Output is correct
14 Correct 2 ms 2668 KB Output is correct
15 Correct 2 ms 2668 KB Output is correct
16 Correct 3 ms 2668 KB Output is correct
17 Correct 10 ms 2796 KB Output is correct
18 Correct 10 ms 2796 KB Output is correct
19 Correct 8 ms 2796 KB Output is correct
20 Correct 2 ms 2796 KB Output is correct
21 Correct 4 ms 2796 KB Output is correct
22 Correct 5 ms 2796 KB Output is correct
23 Correct 12 ms 2796 KB Output is correct
24 Correct 14 ms 2796 KB Output is correct
25 Correct 7 ms 2796 KB Output is correct
26 Correct 5 ms 2796 KB Output is correct
27 Correct 3 ms 2796 KB Output is correct
28 Correct 3 ms 2924 KB Output is correct
29 Correct 5 ms 2924 KB Output is correct
30 Correct 3 ms 2796 KB Output is correct
31 Correct 3 ms 2796 KB Output is correct
32 Correct 3 ms 2796 KB Output is correct
33 Execution timed out 3071 ms 11996 KB Time limit exceeded
34 Halted 0 ms 0 KB -