제출 #489477

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
489477		qwe854896	Cats or Dogs (JOI18_catdog)	C++14	100 / 100	269 ms	47116 KiB

catdog

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

#define endl '\n'
#define pb emplace_back
#define LC(i) (i << 1)
#define RC(i) ((i << 1) | 1)
#define IOS ios::sync_with_stdio(false); cin.tie(nullptr)

using ll  = long long;
using vi  = vector <int>;

const ll INF = 100000000000007;
const int V = 200005;

/* Helper */
void chmin(ll& a, ll b) {
    if (b < a) a = b;
}

/* Graph */
int n;
vi g[V];

/* Segment Tree */
struct SegTree {
    struct Node {
        ll c[2][2]; // cat/dog cat/dog
        void init() {
            c[0][0] = c[1][1] = 0;
            c[0][1] = c[1][0] = INF;
        }
        void update(int x, int y) {
            c[0][0] += x;
            c[1][1] += y;
        }
    };

    int n;
    vector <Node> node;
    void init(int n) {
        this->n = n;
        node.resize(n << 3);
        build(1, 0, n - 1);
    }

    void pull(int i) {
        for (int a = 0; a < 2; ++a)
            for (int b = 0; b < 2; ++b)
                node[i].c[a][b] = INF;
        for (int a = 0; a < 2; ++a)
            for (int b = 0; b < 2; ++b)
                for (int c = 0; c < 2; ++c)
                    for (int d = 0; d < 2; ++d)
                        chmin(node[i].c[a][b], node[LC(i)].c[a][c] + (c ^ d) + node[RC(i)].c[d][b]);
    }

    void build(int i, int l, int r) {
        if (l == r) {
            node[i].init();
            return;
        }
        int m = (l + r) >> 1;
        build(LC(i), l, m);
        build(RC(i), m + 1, r);
        pull(i);
    }

    int ui, x, y;
    void update(int i, int l, int r) {
        if (ui < l || r < ui) return;
        if (l == r) {
            node[i].update(x, y);
            return;
        }
        int m = (l + r) >> 1;
        update(LC(i), l, m);
        update(RC(i), m + 1, r);
        pull(i);
    }

    void update(int i, int x, int y, ll &a, ll &b) {
        ui = i;
        this->x = x;
        this->y = y;
        update(1, 0, n - 1);
        query(a, b);
    }

    void query(ll &x, ll &y) {
        ll c = min(node[1].c[0][0], node[1].c[0][1]);
        ll d = min(node[1].c[1][0], node[1].c[1][1]);
        x = min(c, d + 1);
        y = min(c + 1, d);
    }
};

vector <SegTree> tree;

/* HLD */
int sz[V], hs[V];
int pdfs(int x, int px) {
    sz[x] = 1;
    int h = 0;
    for (int y : g[x])
        if (y != px) {
            sz[x] += pdfs(y, x);
            if (sz[y] > h)
                h = sz[y], hs[x] = y;
        }
    return sz[x];
}

int g_p[V];
int g_sz[V];
int g_cnt, v_num[V];
int pos[V];
void hdfs(int x, int px, int num) {
    if (!g_sz[num]) g_p[num] = px;
    pos[x] = g_sz[num]++;
    v_num[x] = num;
    
    if (hs[x] != -1)
        hdfs(hs[x], x, num);

    for (int y : g[x])
        if (y != px && y != hs[x])
            hdfs(y, x, g_cnt++);
}

void initialize(int N, vi A, vi B) {
    n = N;
    for (int i = 0; i < n; ++i)
        g[i].clear();

    for (int i = n - 2; i >= 0; --i)
        g[--A[i]].pb(--B[i]), g[B[i]].pb(A[i]);

    for (int i = 0; i < n; ++i)
        hs[i] = -1;

    pdfs(0, -1);
    g_cnt = 0;
    for (int i = 0; i < n; ++i) g_sz[i] = 0;
    hdfs(0, -1, g_cnt++);

    tree.resize(g_cnt);
    for (int i = 0; i < g_cnt; ++i)
        tree[i].init(g_sz[i]);
}

int update(int i, int x, int y) {
    while (i != -1) {
        int id;
        ll old_x, old_y, new_x, new_y;
        id = v_num[i];
        tree[id].query(old_x, old_y);
        tree[id].update(pos[i], x, y, new_x, new_y);
        x = new_x - old_x;
        y = new_y - old_y;
        i = g_p[id];
    }
    ll a, b;
    tree[0].query(a, b);
    return min(a, b);
}

int st[V];

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

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

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

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