| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1169584 | sleepntsheep | Cats or Dogs (JOI18_catdog) | C++17 | 0 ms | 0 KiB |
#include "catdog.h"
#include <cstdio>
#include <vector>
#include <algorithm>
#define N 111111
struct Mat{
long long a[4]={0};
friend Mat operator*(const Mat &a, const Mat &b) {
Mat c;
c.a[0] = std::min(a.a[0] + b.a[0], a.a[1] + b.a[2]);
c.a[1] = std::min(a.a[0] + b.a[1], a.a[1] + b.a[3]);
c.a[2] = std::min(a.a[2] + b.a[0], a.a[3] + b.a[2]);
c.a[3] = std::min(a.a[2] + b.a[1], a.a[3] + b.a[3]);
return c;
}
};
struct LCT {
struct{
int c[2],pa;
Mat val,prod;
} t[N];
int nrt(int v){return t[t[v].pa].c[0]==v||t[t[v].pa].c[1]==v;}
void pushup(int v){
if(!v)return;
if(t[v].c[0]&&t[v].c[1])t[v].prod=t[t[v].c[1]].prod*t[v].val*t[t[v].c[0]].prod;
else if(t[v].c[0])t[v].prod=t[v].val*t[t[v].c[0]].prod;
else if(t[v].c[1])t[v].prod=t[t[v].c[1]].prod*t[v].val;
else t[v].prod=t[v].val;
}
void rot(int v){
int p=t[v].pa,g=t[p].pa,d=t[p].c[1]==v;
if(nrt(p))t[g].c[t[g].c[1]==p]=v;
if(t[v].c[!d])t[t[v].c[!d]].pa=p;
t[p].c[d]=t[v].c[!d];
t[v].c[!d]=p;
t[v].pa=g;
t[p].pa=v;
pushup(p);
pushup(v);
}
void splay(int v){
for(int p,g;nrt(v);rot(v)){
g=t[p=t[v].pa].pa;
if(nrt(p))rot((t[g].c[1]==p)==(t[p].c[1]==v)?p:v);
}
pushup(v);
}
void access(int v){
for(int w=0;v;v=t[w=v].pa){
splay(v);
auto X=[&](int x,int mul){
auto Ct=std::min(t[x].prod.a[0],t[x].prod.a[2])
,Dg=std::min(t[x].prod.a[1],t[x].prod.a[3]);
t[v].val.a[0]+=std::min(Ct,Dg+1)*mul;
t[v].val.a[2]+=std::min(Ct,Dg+1)*mul;
t[v].val.a[1]+=std::min(Dg,Ct+1)*mul;
t[v].val.a[3]+=std::min(Dg,Ct+1)*mul;
};
X(t[v].c[1],1);
X(w,-1);
t[v].c[1]=w;
pushup(v);
}
}
void link(int v,int w){
access(v);
splay(v);
t[v].pa=w;
}
}lc;
int col[N],n,vis[N];
std::vector<std::vector<int>>g;
void dfs(int u,int p){
if(u-p)lc.link(u,p);
for(auto v:g[u])if(v-p)dfs(v,u);
}
void initialize(int N_, std::vector<int> A, std::vector<int> B) {
n=N_;
g.resize(n+1);
for(int i=0;i+1<n;++i)g[A[i]].push_back(B[i]),g[B[i]].push_back(A[i]);
dfs(1,1);
for(int i=1;i<=n;++i) {
lc.access(i);lc.splay(i);
lc.t[i].val.a[1]=lc.t[i].val.a[2]=1, lc.pushup(i);
}
}
void ski(int v,int m){
int oo=1e6;
//lc.access(v);
lc.splay(v);
if(col[v]==1){
lc.t[v].val.a[1]+=oo*m;
lc.t[v].val.a[3]+=oo*m;
}else if(col[v]==2){
lc.t[v].val.a[0]+=oo*m;
lc.t[v].val.a[2]+=oo*m;
}else{
}
lc.pushup(v);
}
int getans(){
int yy = 1;
return std::min(std::min(lc.t[yy].prod.a[1],lc.t[yy].prod.a[2]),
std::min(lc.t[yy].prod.a[0],lc.t[yy].prod.a[3]));
}
int cat(int v) {
ski(v,-1);
col[v]=1;
ski(v,1);
for(int i=1;i<=n;++i){
lc.access(i);
lc.splay(i);
lc.t[i].val.pt();
lc.t[i].prod.pt();
}
return getans();
}
int dog(int v) {
ski(v,-1);
col[v]=2;
ski(v,1);
for(int i=1;i<=n;++i){
lc.access(i);
lc.splay(i);
lc.t[i].val.pt();
}
return getans();
}
int neighbor(int v) {
ski(v,-1);
col[v]=0;
ski(v,1);
return getans();
}