Submission #482224

#	Time	Username	Problem	Language	Result	Execution time	Memory
482224		SirCovidThe19th	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	433 ms	31684 KiB

catdog

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

#define FOR(i, x, y) for (int i = x; i < y; i++)
#define mat array<array<int, 2>, 2>

const int mx = 1e5 + 5;

int state[mx], par[mx], sz[mx], dep[mx], root[mx], id[mx], psz[mx]; vector<int> adj[mx];

struct segTree{
    int sz = 1; vector<mat> seg; 
    void init(int sz_){ 
        while (sz < sz_) sz *= 2; 
        seg.resize(sz * 2, {}); 
        FOR(i, 1, sz * 2) seg[i][0][1] = seg[i][1][0] = 1e9;
    }
    void comb(mat &cur, mat A, mat B){ 
        FOR(i, 0, 2) FOR(j, 0, 2) cur[i][j] = 1e9;
        FOR(i, 0, 2) FOR(j, 0, 2) FOR(k, 0, 2) FOR(l, 0, 2)
            cur[i][j] = min(cur[i][j], B[i][k] + A[l][j] + (k != l));
    }
    void apply(int i, int dt0, int dt1){
        i += sz;
        seg[i][0][0] += dt0;
        seg[i][1][1] += dt1;
        while (i /= 2) comb(seg[i], seg[i * 2], seg[i * 2 + 1]); 
    }
    void getBestTop(int &A, int &B){ 
        int top0 = min(seg[1][0][0], seg[1][0][1]);
        int top1 = min(seg[1][1][0], seg[1][1][1]); 
        A = min(top0, top1 + 1);
        B = min(top0 + 1, top1);
    }
}trees[mx];

void dfsSZ(int u){
    sz[u] = 1;
    for (int &v : adj[u]) if (v != par[u]){
        par[v] = u; dep[v] = dep[u] + 1;
        dfsSZ(v); 
        sz[u] += sz[v];
        if (sz[v] > sz[adj[u][0]]) swap(v, adj[u][0]);
    }
}
void dfsHLD(int u){
    id[u] = psz[root[u]]++;
    for (int v : adj[u]) if (v != par[u]){
        root[v] = (v == adj[u][0] ? root[u] : v);
        dfsHLD(v);
    }
}
int updSolve(int u, int col, int dt0, int dt1){
    state[u] = col;
    while (u){
        int b0, b1, n0, n1, R = root[u];
        trees[R].getBestTop(b0, b1);
        trees[R].apply(id[u], dt0, dt1);
        trees[R].getBestTop(n0, n1);
        dt0 = n0 - b0; dt1 = n1 - b1;
        u = par[R];
    }
    int ret0, ret1; trees[1].getBestTop(ret0, ret1);
    return min(ret0, ret1);
}
void initialize(int n, vector<int> A, vector<int> B){ 
    FOR(i, 0, n - 1){
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }
    root[1] = id[1] = 1; dfsSZ(1); dfsHLD(1);
    FOR(i, 1, n + 1){
        trees[i].init(psz[i]);
        id[i] = psz[root[i]] - id[i] - 1; 
    }
}
int cat(int i){ return updSolve(i, 0, 0, mx); }
int dog(int i){ return updSolve(i, 1, mx, 0); }
int neighbor(int i){ return !state[i] ? updSolve(i, 0, 0, -mx) : updSolve(i, 1, -mx, 0); }

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