Submission #1163262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163262		InvMOD	Cats or Dogs (JOI18_catdog)	C++20	0 / 100	4 ms	8260 KiB

catdog

#include<bits/stdc++.h>

//#define name "InvMOD"
#ifndef name
    #include "catdog.h"
#endif // name

using namespace std;

#define dbg(x) "[" << #x " = " << (x) << "]"

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

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

const int INF = 1e9;
const int N = 1e5 + 5;

struct Node{
    int dp[2][2];
    Node(int cat = 0, int dog = 0) {
        dp[0][0] = cat;
        dp[1][1] = dog;
        dp[0][1] = dp[1][0] = N;
    }

    friend Node operator + (Node left, Node right){
        Node answer = Node(N, N);
        for(int l = 0; l < 2; l++){
            for(int r = 0; r < 2; r++){
                for(int a = 0; a < 2; a++){
                    for(int b = 0; b < 2; b++){
                        ckmn(answer.dp[l][r], left.dp[l][a] + right.dp[b][r] + (a ^ b));
                    }
                }
            }
        }
        return answer;
    }
};

struct SMT{
    int trsz;
    vector<Node> st;

    void init(int n){
        trsz = n;
        st.resize((n << 2) + 1);
    }

    void update(int id, int l, int r, int x, int cat, int dog){
        if(l == r){
            st[id].dp[0][0] += cat;
            st[id].dp[1][1] += dog;
        }
        else{
            int m = l+r>>1;
            if(x <= m)
                update(id << 1, l, m, x, cat, dog);
            else update(id << 1|1, m+1, r, x, cat, dog);

            st[id] = st[id << 1] + st[id << 1|1];
        }
    }

    void upd(int x, int cat, int dog){
        update(1, 1, trsz, x, cat, dog);
    }

    int cat(){
        return min(st[1].dp[0][1], st[1].dp[0][0]);
    }

    int dog(){
        return min(st[1].dp[1][0], st[1].dp[1][1]);
    }
};

int n, timerDFS, Chain, sz[N], h[N], preDP[2][N];

int par[N], tin[N], head[N], id[N], inChain[N], who[N];

vector<int> adj[N], store_Chain[N];

SMT st[N];

void preDFS(int x, int p){
    sz[x] = 1;
    for(int v : adj[x])if(v != p){
        h[v] = h[x] + 1;
        par[v] = x;
        preDFS(v, x);
        sz[x] += sz[v];
    }
}

void decompose(int x, int p){
    id[x] = Chain;
    tin[x] = ++timerDFS;

    store_Chain[id[x]].push_back(x);
    if(!head[Chain]) head[Chain] = x;
    inChain[x] = (int)store_Chain[id[x]].size();

    int nxt = 0;
    for(int v : adj[x])if(v != p && sz[v] > sz[nxt]) nxt = v;

    if(nxt) decompose(nxt, x);
    for(int v : adj[x])if(v != p && v != nxt){
        ++Chain;
        decompose(v, x);
    }
}


int update(int x, int ncat, int ndog){
    st[id[x]].upd(inChain[x], +ncat, +ndog);
    while(x){
        int v = par[head[id[x]]];
        if(v){
            st[id[v]].upd(inChain[v], -preDP[0][x], -preDP[1][x]);
        }
        preDP[0][x] = min(st[id[x]].cat(), st[id[x]].dog() + 1);
        preDP[1][x] = min(st[id[x]].dog(), st[id[x]].cat() + 1);

        if(v){
            st[id[v]].upd(inChain[v], +preDP[0][x], +preDP[1][x]);
        }

        x = par[head[id[x]]];
    }
    return min(st[1].cat(), st[1].dog());
}


void initialize(int _n, vector<int> u, vector<int> v){
    n = _n;
    for(int i = 0; i < n - 1; i++){
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }

    preDFS(1, -1);
    Chain = 1, timerDFS = 0;
    decompose(1, -1);

    for(int i = 1; i <= Chain; i++){
        st[i].init((int)store_Chain[i].size());
    }
}

int cat(int v){
    who[v] = 1;
    return update(v, 0, n);
}

int dog(int v){
    who[v] = 2;
    return update(v, n, 0);
}

int neighbor(int v){
    int w = (who[v] & 1); who[v] = 0;
    return (w ? update(v, 0, -n) : update(v, -n, 0));
}

#ifdef name
    int32_t main()
    {
        freopen(name".INP", "r", stdin);
        freopen(name".OUT", "w", stdout);

        int n; cin >> n;

        vector<int> A(n), B(n);
        for(int i = 0; i < n - 1; i++){
            cin >> A[i] >> B[i];
        }
        initialize(n, A, B);

        int q; cin >> q;
        while(q--){
            int op, v; cin >> op >> v;

            if(!op){
                cout << cat(v) << "\n";
            }
            else if(op&1) cout << dog(v) << "\n";
            else cout << neighbor(v) << "\n";
        }
        return 0;
    }
#endif // name

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