Submission #1261142

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261142		icebear	Cats or Dogs (JOI18_catdog)	C++20	38 / 100	3093 ms	30364 KiB

catdog

// ~~ icebear ~~
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;

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

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

#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORR(i,a,b) for(int i=(a); i>=(b); --i)
#define REP(i, n) for(int i=0; i<(n); ++i)
#define RED(i, n) for(int i=(n)-1; i>=0; --i)
#define MASK(i) (1LL << (i))
#define BIT(S, i) (((S) >> (i)) & 1)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define task "icebear"

const int MOD = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 1e18 + 27092008;
const int N = 1e5 + 5;
int n, sz[N], par[N], chain[N], pos[N], len[N], state[N];
vector<int> G[N];

struct Node {
    int s[2][2];
    Node(int a = inf, int b = inf, int c = inf, int d = inf) {
        s[0][0] = a; s[0][1] = b;
        s[1][0] = c; s[1][1] = d;
    }

    friend Node combine(const Node &L, const Node &R) {
        Node res;
        REP(i, 2) REP(j, 2) if (L.s[i][j] != inf)
            REP(x, 2) REP(y, 2) if (R.s[x][y] != inf)
                minimize(res.s[i][y], L.s[i][j] + R.s[x][y] + (j != x));
        return res;
    }
};

Node base[3] = {Node(0, inf, inf, 0), Node(0, inf, inf, inf), Node(inf, inf, inf, 0)};
struct SegmentTree {
    vector<Node> node;
    int sz;

    SegmentTree(int n = 0):
        sz(n), node(4 * n + 5) {}

    void build(int id, int l, int r) {
        if (l == r) {
            node[id] = base[0];
            return;
        }
        int mid = l + r >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
        node[id] = combine(node[id << 1], node[id << 1 | 1]);
    }

    void update(int pos, Node val) {
        int id = 1, l = 1, r = sz;
        while(l < r) {
            int mid = l + r >> 1;
            if (pos > mid) id = (id << 1 | 1), l = mid + 1;
            else id = (id << 1), r = mid;
        }
        node[id] = val;
        while(id) {
            id >>= 1;
            node[id] = combine(node[id << 1], node[id << 1 | 1]);
        }
    }

    int get_ans() {
        return min({node[1].s[0][0], node[1].s[1][1], node[1].s[0][1], node[1].s[1][0]});
    }
} it[N];

void dfs(int u, bool create_chain, bool is_head) {
    sz[u] = 1;
    for(int v : G[u]) if (v != par[u]) {
        par[v] = u;
        dfs(v, false, false);
        sz[u] += sz[v];
    }

    if (create_chain == false) return;
    chain[u] = (is_head ? u : chain[par[u]]);
    pos[u] = ++len[chain[u]];
    int heavy = 0;
    for(int &v : G[u]) if (sz[v] > sz[heavy])
        heavy = v;
    for(int v : G[u]) if (v != par[u])
        dfs(v, true, (v != heavy));
}

int sum_child[2][N];
void update(int u) {
    while(u > 0) {
        int head = chain[u];
        Node cur = it[head].node[1];
        // del
        sum_child[0][par[head]] -= min({cur.s[0][0], cur.s[0][1], cur.s[1][0] + 1, cur.s[1][1] + 1});
        sum_child[1][par[head]] -= min({cur.s[1][0], cur.s[1][1], cur.s[0][0] + 1, cur.s[0][1] + 1});

        // recalc
        cur = base[state[u]];
        if (cur.s[0][0] != inf) cur.s[0][0] += sum_child[0][u];
        if (cur.s[1][1] != inf) cur.s[1][1] += sum_child[1][u];
        it[head].update(pos[u], cur);

        // add
        cur = it[head].node[1];
        sum_child[0][par[head]] += min({cur.s[0][0], cur.s[0][1], cur.s[1][0] + 1, cur.s[1][1] + 1});
        sum_child[1][par[head]] += min({cur.s[1][0], cur.s[1][1], cur.s[0][0] + 1, cur.s[0][1] + 1});

        u = par[head];
    }
}

int cat(int v) {state[v] = 1; update(v); return it[1].get_ans();}
int dog(int v) {state[v] = 2; update(v); return it[1].get_ans();}
int neighbor(int v) {state[v] = 0; update(v); return it[1].get_ans();}

void initialize(int N, vector<int> A, vector<int> B) {
    n = N;
    REP(i, (int)A.size()) {
        G[A[i]].pb(B[i]);
        G[B[i]].pb(A[i]);
    }
    dfs(1, true, true);
    FOR(i, 1, n) if (i == chain[i]) {
        it[i] = SegmentTree(len[i]);
        it[i].build(1, 1, len[i]);
    }
}

// int main() {
//     ios_base::sync_with_stdio(0);
//     cin.tie(0); cout.tie(0);
//     if (fopen(task".inp", "r")) {
//         freopen(task".inp", "r", stdin);
//         freopen(task".out", "w", stdout);
//     }
//     initialize(5, {1, 2, 2, 4}, {2, 3, 4, 5});
//     cout << cat(3) << ' ' << dog(5) << '\n';
//     cout << cat(2) << ' ' << dog(1) << '\n';
//     cout << neighbor(2) << '\n';
//     return 0;
// }

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