Submission #674313

#	Time	Username	Problem	Language	Result	Execution time	Memory
674313		jeroenodb	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	350 ms	24388 KiB

catdog

#include "catdog.h"
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;

struct F {
    int mat[2][2] = {{0,1},{1,0}};
    friend F op(const F& u,const F& v) {
        F res = {oo,oo,oo,oo};
        for(int i : {0,1}) for(int j : {0,1}) for(int k : {0,1}) {
            res.mat[i][k] = min(res.mat[i][k], u.mat[i][j]+v.mat[j][k]);
        }
        return res;
    }
    int get() {
        int ans=oo;
        for(int i : {0,1}) for(int j : {0,1}) ans = min(ans,mat[i][j]);
        return ans;
    }
    pair<ll,ll> dp() {
        int x=oo,y=oo;
        for(int i : {0,1}) {
            x = min(x,mat[i][0]);
            y = min(y,mat[i][1]);
        }
        return {x,y};
    }
};
template<class T> struct splaytree {
    // flip
    #define L c[0]
    #define R c[1]
    struct node {
        T val;
        node *c[2] = {NULL,NULL}, *par =NULL;
        bool pathtop=true;
        node(const T& v) : val(v) {}
        node() {}
    };
    static void recalc(node* at) {
        at->val.recalc();
        if(at->L) at->val.recalc(at->L->val,0);
        if(at->R) at->val.recalc(at->R->val,1);
    }
    static void print(node* n) {
        if(n==NULL) return;
        print(n->L);
        cout << n->val << ' ';
        print(n->R);
    }
    static void rotate(node* n) {
        // Precondition: n is not the root, Postcondition: rotates n to the place of its parent
        assert(n and !n->pathtop and n->par);
        node* par = n->par;
        if(!par->pathtop) {
            auto gp = par->par;
            if(gp->L==par) gp->L=n;
            else if(gp->R==par) gp->R=n;
        }
        n->par = par->par;
        bool b= n!=par->L;
        #define l c[b]
        #define r c[b^1]
        par->l = n->r; // Fix right child of current node
        if(n->r) n->r->par = par;
        n->r = par; // Put parent under current node
        #undef l
        #undef r
        par->par = n;
        swap(par->pathtop, n->pathtop);
        recalc(par), recalc(n);
    }
    static void splay(node* n) {
        while(!n->pathtop) {
            if(n->par->pathtop) {
                rotate(n);
            } else {
                auto p = n->par, gp = p->par;
                // Double rotations
                if((p->L==n) == (gp->L==p)) rotate(p);
                else rotate(n);
                rotate(n);
            }
        }
    }
    #undef L
    #undef R
};

struct vertex{
    F mine,sub;
    vertex(){}
    void recalc(const vertex& o,bool rev=false) {
        sub  = rev?op(o.sub,sub):op(sub,o.sub);
    }
    void recalc() {
        sub=mine;
    }
}; 
array<array<ll,2>,2> matSingle[3] = {{0,1,1,0}, {0,oo,1,oo}, {oo,1,oo,0}};
struct linkcut {
    // initially the linkcut tree consists of n disconnected size 1 trees.
    typedef splaytree<vertex> bst;
    typedef bst::node node;
    int n=0;
    node* t=NULL;
    linkcut() {}
    linkcut(int nn) {
        n=nn;
        t = new node[n];
        for(int i=0;i<n;++i) {
            t[i] = node(vertex{});
        }
    }
    void attach(node* at, int sgn=1) {
        auto& f = at->par->val.mine;
        auto [x,y] = at->val.sub.dp();
        f.mat[0][1]+=sgn*min(x+1,y);
        f.mat[1][1]+=sgn*min(x+1,y);
        f.mat[0][0]+=sgn*min(x,y+1);
        f.mat[1][0]+=sgn*min(x,y+1);
    }
    void attach(int i, int sgn=1) {
        attach(t+i,sgn);
    }

    node* expose(int u) {
        node *at = NULL, *par = t+u;
        for(;par; at=par,par = par->par) {
            bst::splay(par);
            if(par->c[1]) {
                attach(par->c[1]);
                par->c[1]->pathtop = true;
                par->c[1] = NULL;
            }
            if(at) {
                attach(at,-1);
                at->pathtop = false;
            }
            par->c[1] = at;
            bst::recalc(par);     
        }
        bst::splay(t+u);
        return t+u;
    }
    void link(int u, int v) { // precondition: u is root of tree
        t[u].par = t+v; // connect with unmarked edge
        attach(u);
    }
    ll calc() {
        auto root = expose(0);
        return root->val.sub.get();
    }
    void update(int i, int old, int nw) {
        expose(i);
        for(int j=0;j<2;++j) for(int k=0;k<2;++k) {
            t[i].val.mine.mat[j][k]+=matSingle[nw][j][k]-matSingle[old][j][k];
        }
        
        bst::recalc(t+i);
    }
};
vvi adj;
linkcut tree;
void dfs(int at, int from) {
    for(int to : adj[at]) if(to!=from) {
        dfs(to,at);
        tree.link(to,at);
    }
}
int n;
vi typ;
void initialize(int N, std::vector<int> A, std::vector<int> B) {
    n=N;
    adj.resize(n);
    for(int i=0;i<n-1;++i) {
      adj[A[i]-1].push_back(B[i]-1);
      adj[B[i]-1].push_back(A[i]-1);
    }
    tree = linkcut(n);
    typ.resize(n);
    dfs(0,0);
}
int update(int v, int a) {
  tree.update(v,typ[v],a);
  typ[v]=a;
  return tree.calc();
}
int cat(int v) {
  return update(v-1,2);
}

int dog(int v) {
  return update(v-1,1);
}

int neighbor(int v) {
  return update(v-1,0);
}

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