Submission #887373

#	Time	Username	Problem	Language	Result	Execution time	Memory
887373		hmm789	Cats or Dogs (JOI18_catdog)	C++14	100 / 100	145 ms	32880 KiB

catdog

#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
#define INF 1000000000

struct node {
    int s, e, m, v[2][2];
    node *l, *r;
    node(int _s, int _e) {
        s = _s, e = _e, m = (s+e)/2;
        if(s != e) {
            v[0][0] = v[1][1] = 0;
            v[0][1] = v[1][0] = 1;
            l = new node(s, m);
            r = new node(m+1, e);
        } else {
            v[0][0] = v[1][1] = 0;
            v[0][1] = v[1][0] = INF;
        }
    }
    void update(int x, int a, int b) {
        if(s == e) {
            v[0][0] += a;
            v[1][1] += b;
            return;
        } else if(x > m) r->update(x, a, b);
        else l->update(x, a, b);
        for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++) v[i][j] = INF;
        for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++) for(int k = 0; k < 2; k++) for(int w = 0; w < 2; w++) {
            v[i][j] = min(v[i][j], l->v[i][k]+(k^w)+r->v[w][j]);
        }
    }
    pair<int, int> query() {
        int a = min(v[0][0], v[0][1]);
        int b = min(v[1][0], v[1][1]);
        return {min(a, b+1), min(b, a+1)};
    }
} *root[100000];

int n;
vector<int> adj[100000];
int heavy[100000], head[100000], pos[100000], par[100000], grp[100000], gsz[100000], cur=1;
int a[100000];

int dfs(int x, int p) {
    int sz = 1, mx = 0;
    par[x] = p;
    for(int i : adj[x]) if(i != p) {
        int child = dfs(i, x);
        sz += child;
        if(child > mx) {
            heavy[x] = i;
            mx = child;
        }
    }
    return sz;
}

void dfs2(int x, int h) {
    head[x] = h;
    grp[x] = grp[h];
    pos[x] = gsz[grp[x]]++;
    if(heavy[x] != -1) dfs2(heavy[x], h);
    for(int i : adj[x]) if(i != par[x] && i != heavy[x]) {
        grp[i] = cur++;
        dfs2(i, i);
    }
}

void initialize(int N, std::vector<int> A, std::vector<int> B) {
    n = N;
    for(int i = 0; i < n-1; i++) {
        A[i]--; B[i]--;
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }
    memset(heavy, -1, sizeof(heavy));
    dfs(0, -1);
    dfs2(0, 0);
    for(int i = 0; i < cur; i++) root[i] = new node(0, gsz[i]-1);
}

int update(int x, int a, int b) {
    pair<int, int> prv, cur;
    for(; x != -1; x = par[head[x]]) {
        prv = root[grp[x]]->query();
        root[grp[x]]->update(pos[x], a, b);
        cur = root[grp[x]]->query();
        a = cur.first-prv.first; b = cur.second-prv.second;
    }
    return min(cur.first, cur.second);
}

int cat(int v) {
    v--;
    a[v] = 1;
    return update(v, 0, n);
}

int dog(int v) {
    v--;
    a[v] = 2;
    return update(v, n, 0);
}

int neighbor(int v) {
    v--;
    if(a[v] == 1) {
        a[v] = 0;
        return update(v, 0, -n);
    } else {
        a[v] = 0;
        return update(v, -n, 0);
    }
}

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