Submission #58582

#	Time	Username	Problem	Language	Result	Execution time	Memory
58582		imeimi2000	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	418 ms	81468 KiB

catdog

#include "catdog.h"
#include <algorithm>
#include <functional>

using namespace std;
typedef pair<int, int> pii;
typedef long long llong;

const llong inf = 1e16;
const int MAXN = 1e6;

struct node {
    llong val[2][2];
    node() {
        val[0][0] = val[1][1] = 0;
        val[0][1] = val[1][0] = inf;
    }
    node operator+(const node &p) const {
        node ret;
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {
                ret.val[i][j] = inf;
                for (int k = 0; k < 2; ++k) {
                    for (int l = 0; l < 2; ++l) {
                        ret.val[i][j] = min(ret.val[i][j]
                            , val[i][k] + p.val[l][j] + (k ^ l));
                    }
                }
            }
        }
        return ret;
    }
};

struct segtree {
    vector<node> val;
    int sz;
    void init(int i, int s, int e) {
        if (s == e) return;
        int m = (s + e) / 2;
        init(i << 1, s, m);
        init(i << 1 | 1, m + 1, e);
        val[i] = val[i << 1] + val[i << 1 | 1];
    }
    
    void init(int _sz) {
        int s = 1;
        sz = _sz;
        while (s < (sz << 1)) s <<= 1;
        val.resize(s);
        init(1, 1, sz);
    }
    
    void update(int i, int s, int e, int x, llong v0, llong v1) {
        if (s == e) {
            val[i].val[0][0] += v0;
            val[i].val[1][1] += v1;
            return;
        }
        int m = (s + e) / 2;
        if (x <= m) update(i << 1, s, m, x, v0, v1);
        else update(i << 1 | 1, m + 1, e, x, v0, v1);
        val[i] = val[i << 1] + val[i << 1 | 1];
    }
    
    void update(int i, llong x0, llong x1) {
        update(1, 1, sz, i, x0, x1);
    }
    
    pii query() const {
        int x = min(val[1].val[0][0], val[1].val[0][1]);
        int y = min(val[1].val[1][0], val[1].val[1][1]);
        return pii(min(x, y + 1), min(x + 1, y));
    }
} seg[100001];

int n;
vector<int> edge[100001];
int sz[100001];
int pathPar[100001];
int pathPos[100001];
int par[100001];
int st[100001];

void dfsSize(int x, int p) {
    par[x] = p;
    sz[x] = 1;
    for (int i : edge[x]) {
        if (i == p) continue;
        dfsSize(i, x);
        sz[x] += sz[i];
    }
}

void dfsDecomp(int x, int p) {
    int hpath = 0;
    for (int i : edge[x]) {
        if (i == p) continue;
        if (sz[x] <= (sz[i] << 1)) {
            hpath = i;
            break;
        }
    }
    if (hpath == 0) seg[pathPar[x]].init(pathPos[x]);
    for (int i : edge[x]) {
        if (i == p) continue;
        if (i != hpath) {
            pathPar[i] = i;
            pathPos[i] = 1;
        }
        else {
            pathPar[i] = pathPar[x];
            pathPos[i] = pathPos[x] + 1;
        }
        dfsDecomp(i, x);
    }
}

void initialize(int N, vector<int> A, vector<int> B) {
    n = N;
    for (int i = 0; i < n - 1; ++i) {
        edge[A[i]].push_back(B[i]);
        edge[B[i]].push_back(A[i]);
    }
    dfsSize(1, 0);
    pathPar[1] = 1;
    pathPos[1] = 1;
    dfsDecomp(1, 0);
}

void update(int x, int v0, int v1) {
    while (x) {
        int path = pathPar[x];
        int pr0, pr1, nx0, nx1;
        tie(pr0, pr1) = seg[path].query();
        seg[path].update(pathPos[x], v0, v1);
        tie(nx0, nx1) = seg[path].query();
        v0 = nx0 - pr0;
        v1 = nx1 - pr1;
        x = par[pathPar[x]];
    }
}

int getAns() {
    int x, y;
    tie(x, y) = seg[1].query();
    return min(x, y);
}

int cat(int v) {
    st[v] = 1;
    update(v, MAXN, 0);
    return getAns();
}

int dog(int v) {
    st[v] = 2;
    update(v, 0, MAXN);
    return getAns();
}

int neighbor(int v) {
    if (st[v] == 1) update(v, -MAXN, 0);
    else update(v, 0, -MAXN);
    st[v] = 0;
    return getAns();
}

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