제출 #1169585

#제출 시각아이디문제언어결과실행 시간메모리
1169585sleepntsheepCats or Dogs (JOI18_catdog)C++17
0 / 100
3 ms9028 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); return getans(); } int dog(int v) { ski(v,-1); col[v]=2; ski(v,1); return getans(); } int neighbor(int v) { ski(v,-1); col[v]=0; ski(v,1); return getans(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...