Submission #1278492

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278492		wonderful	Cats or Dogs (JOI18_catdog)	C++20	100 / 100	164 ms	69064 KiB

catdog

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

typedef long long ll;
#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()

template<class T1, class T2>
bool maximize(T1 &a, T2 b){ if (a < b){ a = b; return true; } return false; }

template<class T1, class T2>
bool minimize(T1 &a, T2 b){ if (a > b){ a = b; return true; } return false; }

const ll INF = 1e18;

int n;
vector<int> adj[1000005];
int child[1000005], big[1000005];
int par[1000005], head[1000005], rev[1000005], pos[1000005], curPos, sz[1000005];
int cur[1000005];

void dfs(int u, int p){
    child[u] = 1;
    big[u] = -1;
    for (auto v : adj[u]){
        if (v == p) continue;
        dfs(v, u);
        child[u] += child[v];
        if (big[u] == -1 || child[big[u]] < child[v]) big[u] = v;
    }
}

void decompose(int u, int h, int p){
    pos[u] = ++curPos;
    par[u] = p;
    rev[curPos] = u;
    head[u] = h;
    sz[h]++;
    if (big[u] != -1) decompose(big[u], h, u);
    for (auto v : adj[u]){
        if (v == p || v == big[u]) continue;
        decompose(v, v, u);
    }
}

struct Node{
    ll x[2][2];
};

Node combine(Node a, Node b){
    Node res;
    for (int i = 0; i <= 1; i++)
        for (int j = 0; j <= 1; j++)
            res.x[i][j] = 1e9;

    for (int i = 0; i <= 1; i++)
        for (int j = 0; j <= 1; j++)
            for (int k = 0; k <= 1; k++)
                for (int l = 0; l <= 1; l++)
                    res.x[i][j] = min(res.x[i][j], a.x[i][k] + b.x[l][j] + (k ^ l));

    return res;
}

struct SegTree{
    vector<Node> st;
    int n;
    void init(int _n){ n = _n; st.assign(4*n+5, {}); }

    void build(int id, int l, int r){
        if (l == r){
            st[id].x[0][0] = st[id].x[1][1] = 0;
            st[id].x[0][1] = st[id].x[1][0] = 1e9;
            return;
        }
        int mid = (l + r) >> 1;
        build(id*2, l, mid);
        build(id*2+1, mid+1, r);
        st[id] = combine(st[id*2], st[id*2+1]);
    }

    void update(int id, int l, int r, int p, int va, int vb){
        if (l == r){
            st[id].x[0][0] += va;
            st[id].x[1][1] += vb;
            return;
        }
        int mid = (l + r) >> 1;
        if (p <= mid) update(id*2, l, mid, p, va, vb);
        else update(id*2+1, mid+1, r, p, va, vb);
        st[id] = combine(st[id*2], st[id*2+1]);
    }

    pair<int,int> get(){
        int c = min(st[1].x[0][0], st[1].x[0][1]);
        int d = min(st[1].x[1][1], st[1].x[1][0]);
        return {min(c, d+1), min(c+1, d)};
    }
};

SegTree seg[1000005];

void updatePath(int u, int va, int vb){
    while (u){
        int h = head[u];
        auto [c, d] = seg[h].get();
        seg[h].update(1, 1, sz[h], pos[u]-pos[h]+1, va, vb);
        auto [c1, d1] = seg[h].get();
        va = c1 - c;
        vb = d1 - d;
        u = par[h];
    }
}

int cat(int x){
    cur[x] = 1;
    updatePath(x, 0, 1e9);
    auto [c, d] = seg[1].get();
    return min(c, d);
}

int dog(int x){
    cur[x] = 2;
    updatePath(x, 1e9, 0);
    auto [c, d] = seg[1].get();
    return min(c, d);
}

int neighbor(int x){
    updatePath(x, -1e9*(cur[x] != 1), -1e9*(cur[x] != 2));
    cur[x] = 0;
    auto [c, d] = seg[1].get();
    return min(c, d);
}

void initialize(int N, vector<int> A, vector<int> B){
    n = N;
    for (int i = 0; i < n-1; i++){
        int u = A[i], v = B[i];
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 0);
    decompose(1, 1, 0);
    for (int i = 1; i <= n; i++){
        if (head[i] == i){
            seg[i].init(sz[i]);
            seg[i].build(1, 1, sz[i]);
        }
    }
}

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