Submission #917126

#	Time	Username	Problem	Language	Result	Execution time	Memory
917126		GrindMachine	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	553 ms	22096 KiB

catdog

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

refs:
edi
https://oj.uz/submission/374896

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

template<typename T>
struct segtree {
    // https://codeforces.com/blog/entry/18051

    /*=======================================================*/

    struct data {
        array<array<int,2>,2> dp;
        bool active;

        data(){
            rep(i,2){
                rep(j,2){
                    dp[i][j] = inf1;
                }
            }
            active = false;
        }
    };

    data neutral = data();

    data merge(data &left, data &right) {
        if(!left.active and !right.active) return left;
        if(!right.active) return left;
        if(!left.active) return right;
        
        data curr;
        curr.active = true;

        rep(i,2){
            rep(j,2){
                rep(k,2){
                    rep(l,2){
                        amin(curr.dp[i][l],left.dp[i][j]+right.dp[k][l]+(j!=k));
                    }
                }
            }
        }

        return curr;
    }

    void create(int i, T v) {

    }

    void modify(int i, T v) {
        tr[i] = neutral;
        tr[i].dp[0][0] = v.ff;
        tr[i].dp[1][1] = v.ss;
        tr[i].active = true;
    }

    /*=======================================================*/

    int n;
    vector<data> tr;

    segtree() {

    }

    segtree(int siz) {
        init(siz);
    }

    void init(int siz) {
        n = siz;
        tr.assign(2 * n, neutral);
    }

    void build(vector<T> &a, int siz) {
        rep(i, siz) create(i + n, a[i]);
        rev(i, n - 1, 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
    }

    void pupd(int i, T v) {
        modify(i + n, v);
        for (i = (i + n) >> 1; i; i >>= 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
    }

    data query(int l, int r) {
        data resl = neutral, resr = neutral;

        for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
            if (l & 1) resl = merge(resl, tr[l++]);
            if (!(r & 1)) resr = merge(tr[r--], resr);
        }

        return merge(resl, resr);
    }
};

vector<int> adj[N];
vector<int> a(N); // 0 = none, 1 = cat, 2 = dog
vector<int> subsiz(N);
vector<int> depth(N), par(N);

void dfs1(int u, int p){
    subsiz[u] = 1;
    if(p != -1) par[u] = p;
    trav(v,adj[u]){
        if(v == p) conts;
        depth[v] = depth[u]+1;
        dfs1(v,u);
        subsiz[u] += subsiz[v];
    }
}

vector<int> pos(N), head(N), chain_siz(N);
int timer = 1;

void dfs2(int u, int p, int h){
    pos[u] = timer++;
    head[u] = h;
    chain_siz[h]++;

    pii mx = {-inf1,-1};
    trav(v,adj[u]){
        if(v == p) conts;
        pii px = {subsiz[v],v};
        amax(mx,px);
    }

    int heavy = mx.ss;
    if(heavy != -1){
        dfs2(heavy,u,h);
    }

    trav(v,adj[u]){
        if(v == p or v == heavy) conts;
        dfs2(v,u,v);
    }
}

segtree<pii> st;

void initialize(int n, std::vector<int> A, std::vector<int> B) {
    rep(i,n-1){
        int u = A[i], v = B[i];
        adj[u].pb(v), adj[v].pb(u);
    }

    dfs1(1,-1);
    dfs2(1,-1,1);
    st = segtree<pii>(n+5);
    rep1(i,n) st.pupd(i,{0,0});
}

vector<int> sum1(N), sum2(N);

int get_ans(){
    auto dp = st.query(pos[1],pos[1]+chain_siz[1]-1).dp;

    int ans = inf1;

    rep(i,2){
        rep(j,2){
            amin(ans,dp[i][j]);
        }
    }

    return ans;
}

void rem(int u){
    while(u){
        if(u == head[u]){
            auto dp = st.query(pos[u],pos[u]+chain_siz[u]-1).dp;
            int cat = min(dp[0][0],dp[0][1]);
            int dog = min(dp[1][0],dp[1][1]);
            sum1[par[u]] -= min(cat,dog+1);
            sum2[par[u]] -= min(cat+1,dog);
            u = par[u];
        }
        else{
            u = head[u];
        }
    }
}

void add(int u){
    while(u){
        {
            pii px = {sum1[u],sum2[u]};

            if(a[u] == 1){
                px.ss = inf1;
            }
            else if(a[u] == 2){
                px.ff = inf1;
            }

            st.pupd(pos[u],px);
        }

        if(u == head[u]){
            auto dp = st.query(pos[u],pos[u]+chain_siz[u]-1).dp;
            int cat = min(dp[0][0],dp[0][1]);
            int dog = min(dp[1][0],dp[1][1]);
            sum1[par[u]] += min(cat,dog+1);
            sum2[par[u]] += min(cat+1,dog);
            u = par[u];
        }
        else{
            u = head[u];
        }
    }
}

void change_state(int u, int val){
    rem(u);
    a[u] = val;
    add(u);
}
 
int cat(int v) {
    change_state(v,1);
    return get_ans();
}
 
int dog(int v) {
    change_state(v,2);
    return get_ans();
}
 
int neighbor(int v) {
    change_state(v,0);
    return get_ans();
}

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