Submission #1169585

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169585		sleepntsheep	Cats or Dogs (JOI18_catdog)	C++17	0 / 100	3 ms	9028 KiB

catdog

#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();
}

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