Submission #1147384

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147384		sonamoo	Cats or Dogs (JOI18_catdog)	C++20	100 / 100	434 ms	28740 KiB

catdog

#include "catdog.h"
#include <bits/stdc++.h>
#define pii pair<int,int>
#define ll long long int
#define SIZE 100005
#define all(v) v.begin(), v.end()
#define pb push_back
#define MOD 1000000007
#define INF 1000000007

using namespace std;

int n;
vector<int> g[SIZE] , child[SIZE];
int C[SIZE];
int sz[SIZE] , dep[SIZE] , pa[SIZE];
int num[SIZE] , TOP[SIZE] , BOT[SIZE];
int L[SIZE][2];

struct ST{
    struct Node {
        int v[2][2] , e;
        int getmin() const { return min(min(v[0][0] , v[0][1]) , min(v[1][0] , v[1][1])); }

        Node operator+(const Node& b) {
            if (e==1) return b;
            if (b.e==1) return {v[0][0] , v[0][1] , v[1][0] , v[1][1] , e};
            Node val={INF , INF , INF , INF , 0};
            for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) for (int k = 0; k < 2; k++) for (int l = 0; l < 2; l++) val.v[i][l] = min(val.v[i][l] , v[i][j]+b.v[k][l]+(j!=k));
            return val;
        }
    };

    Node tree[SIZE*4];

    //build

    void build(int nod , int nl , int nr) {
        if (nl == nr) {
            tree[nod] = {0 , INF , INF , 0 , 0};
            return;
        }
        int m = (nl+nr)/2;
        build(nod*2 , nl , m); build(nod*2+1 , m+1 , nr);
        tree[nod] = tree[nod*2]+tree[nod*2+1];
    }

    //query

    Node query(int nod , int nl , int nr , int l , int r) {
        if (nr < l || r < nl) return {INF , INF , INF , INF , 1};
        if (l <= nl && nr <= r) return tree[nod];
        int m = (nl+nr)/2;
        Node Lval = query(nod*2 , nl , m , l , r);
        Node Rval = query(nod*2+1 , m+1 , nr , l , r);
        return Lval+Rval;
    }

    //update

    void update(int nod , int nl , int nr , int idx , Node val) {
        if (nr < idx || idx < nl) return;
        if (nl == nr) { tree[nod]=val; return; }
        int m = (nl+nr)/2;
        update(nod*2 , nl , m , idx , val);
        update(nod*2+1 , m+1 , nr , idx , val);
        tree[nod] = tree[nod*2]+tree[nod*2+1];
    }

    pii G(Node X) {
        return {min(X.v[0][0] , X.v[0][1]) , min(X.v[1][0] , X.v[1][1])};
    }

    void upd(int idx) {
        Node ret = {INF , INF , INF , INF , 0};
        if (C[idx]!=2) ret.v[0][0] = L[idx][0];
        if (C[idx]!=1) ret.v[1][1] = L[idx][1];
        update(1 , 1 , n , idx , ret);
    }
}seg;

void bui(int here , int p) {
    for (auto t : g[here]) {
        if (p == t) continue;
        pa[t] = here;
        dep[t] = dep[here]+1;
        child[here].pb(t); bui(t , here);
    }
}

void getsz(int here) {
    sz[here]=1;
    for (auto &t : child[here]) {
        getsz(t);
        sz[here] += sz[t];
        if (sz[t] > sz[child[here].front()]) swap(child[here].front() , t);
    }
}

int pv;
void hld(int here) {
    num[here] = ++pv;
    bool isFirst=true;
    for (auto t : child[here]) {
        if (isFirst) {
            TOP[t] = TOP[here];
            isFirst=false;
        }
        else TOP[t]=t;
        hld(t);
    }
    BOT[here] = child[here].size() > 0 ? BOT[child[here][0]] : here;
}

int solve(int idx , int x) {
    C[num[idx]] = x;
    while(TOP[idx]!=1) {
        auto [prv0 , prv1] = seg.G(seg.query(1 , 1 , n , num[TOP[idx]] , num[BOT[idx]]));
        seg.upd(num[idx]);
        auto [cur0 , cur1] = seg.G(seg.query(1 , 1 ,  n , num[TOP[idx]] , num[BOT[idx]]));
        idx = pa[TOP[idx]];
        L[num[idx]][0] += min(cur0 , cur1+1)-min(prv0 , prv1+1);
        L[num[idx]][1] += min(cur0+1 , cur1)-min(prv0+1 , prv1);
    }
    seg.upd(num[idx]);
    return seg.query(1 , 1 , n , num[TOP[idx]] , num[BOT[idx]]).getmin();
}

void initialize(int N, std::vector<int> A, std::vector<int> B) {
    n = N;
    for (int i = 0; i < A.size(); i++) {
        g[A[i]].pb(B[i]); g[B[i]].pb(A[i]);
    }

    bui(1,-1);
    getsz(1);
    TOP[1]=1;
    hld(1);

    seg.build(1 , 1 , n);
}

int cat(int v) {
  return solve(v , 1);
}

int dog(int v) {
  return solve(v , 2);
}

int neighbor(int v) {
  return solve(v , 3);
}

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