Submission #304815

#	Time	Username	Problem	Language	Result	Execution time	Memory
304815		gevacrt	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	1038 ms	27128 KiB

catdog

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

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

#define INF 100010
#define MOD 1000000007
#define all(x) x.begin(), x.end()

struct nda{
    int cc = 0, cd = INF;
    int dc = INF, dd = 0;
    bool eq(nda v){
        return (cc == v.cc) && (cd == v.cd) &&
        (dc == v.dc) && (dd == v.dd);
    }
};

nda mu(nda a, nda b){
    if(a.eq({-1,-1,-1,-1})) return b;
    if(b.eq({-1,-1,-1,-1})) return a;
    
    nda ans;
    ans.cc = min({a.cc+b.cc, a.cc+b.dc+1, a.cd+b.cc+1, a.cd+b.dc});
    ans.cd = min({a.cc+b.cd, a.cc+b.dd+1, a.cd+b.cd+1, a.cd+b.dd});
    ans.dc = min({a.dc+b.cc, a.dc+b.dc+1, a.dd+b.cc+1, a.dd+b.dc});
    ans.dd = min({a.dc+b.cd, a.dc+b.dd+1, a.dd+b.cd+1, a.dd+b.dd});
    return ans;
}

class SegTree{
    vector<nda> st; int l, r;

    void Update(int node, int l, int r, int L, int R, int v0, int v1){
        if(r < L or R < l) return;
        if(L <= l and r <= R){
            st[node].cc += v0;
            st[node].dd += v1;
            return;
        }

        int m = (l+r)>>1;
        Update(node*2, l, m, L, R, v0, v1);
        Update(node*2+1, m+1, r, L, R, v0, v1);
        st[node] = mu(st[node*2], st[node*2+1]);
        return;
    }

    nda Query(int node, int l, int r, int L, int R){
        if(r < L or R < l) return nda{-1,-1,-1,-1};
        if(L <= l and r <= R) return st[node];
        int m = (l+r)>>1;
        auto v1 = Query(node*2, l, m, L, R);
        auto v2 = Query(node*2+1, m+1, r, L, R);
        return mu(v1, v2);
    }

    public:
        SegTree(int l, int r){
            int sz = (r-l+1);
            st.resize(4*sz);
            this->l = l, this->r = r;
        }

        void Update(int L, int R, int v0, int v1){
            Update(1, l, r, L, R, v0, v1);
            return;
        }

        nda Query(int L, int R){
            return Query(1, l, r, L, R);
        }
};

class HLD{
    vi heavy, head, pos; // [next node, root of chain, index]
    vi parent, depth;
    int pos_timer = 0;
    SegTree ST;

    vi ende;

    int dfs(int u, const vvi &adj){
        int subtree_size = 1, max_size = 0;
        for(auto v : adj[u]){
            if(v == parent[u]) continue;
            parent[v] = u, depth[v] = depth[u]+1;
            int child_subtree_size = dfs(v, adj);
            subtree_size += child_subtree_size;
            if(max_size < child_subtree_size){
                max_size = child_subtree_size;
                heavy[u] = v;
            }
        }
        return subtree_size;
    }

    void decompose(int u, int h, const vvi &adj){
        head[u] = h; pos[u] = pos_timer++;
        ende[h] = pos[u];

        if(heavy[u] != -1)
            decompose(heavy[u], h, adj);
        for(auto v : adj[u]){
            if(v == parent[u] || v == heavy[u]) continue;
            decompose(v, v, adj);
        }
        return;
    }

    public:
        HLD(const vvi &adj) : ST(0, adj.size()-1){
            int N = adj.size(); // !!0 based indexing!!
            heavy = vi(N, -1), head = vi(N), pos = vi(N);
            parent = vi(N), depth = vi(N);
            ende = vi(N);

            dfs(0, adj);
            decompose(0, 0, adj);
        }

        int Update(int a, int v0, int v1){
            for(int u = a; true; u = parent[head[u]]){
                auto prev = ST.Query(pos[head[u]], ende[head[u]]);
                ST.Update(pos[u], pos[u], v0, v1);
                auto next = ST.Query(pos[head[u]], ende[head[u]]);
                v0 = min({next.cc, next.cd, next.dc+1, next.dd+1}) - 
                    min({prev.cc, prev.cd, prev.dc+1, prev.dd+1});
                v1 = min({next.dd, next.dc, next.cc+1, next.cd+1}) -
                    min({prev.dd, prev.dc, prev.cc+1, prev.cd+1});

                if(head[u] == 0){
                    return min({next.cc, next.cd, next.dc, next.dd});
                }
            }
            return -1; // impossible case
        }
};

vi col; HLD hvt(vvi(1));
void initialize(int n, vi a, vi b){
    vvi adj(n); col = vi(n, 0);
    for(int x = 0; x < n-1; x++){
        adj[a[x]-1].push_back(b[x]-1);
        adj[b[x]-1].push_back(a[x]-1);
    }
    hvt = HLD(adj);
    return;
}

// cat ==> 0
int cat(int v){
    v--; col[v] = 1;
    return hvt.Update(v, 0, INF);
}

// dog ==> 1
int dog(int v){
    v--; col[v] = 2;
    return hvt.Update(v, INF, 0);
}

int neighbor(int v){
    v--; int tp = col[v]; col[v] = 0;
    if(tp == 1) return hvt.Update(v, 0, -INF);
    return hvt.Update(v, -INF, 0);
}

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