Submission #1169244

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

catdog

#include "catdog.h"
#include <cstdio>
#include <vector>
#include <algorithm>

#define N 111111

int col[N];

struct Mat{
	long long a[4];
	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;
	}
	void pt() {
		return ;
		printf("  [ %d %d %d %d]\n",a[0],a[1],a[2],a[3]);
	}
};

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(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[p].pa=v;t[v].pa=g;
		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);
			t[v].val.a[0]+=std::min(t[t[v].c[1]].prod.a[0],t[t[v].c[1]].prod.a[3]+1);
			t[v].val.a[2]+=std::min(t[t[v].c[1]].prod.a[0],t[t[v].c[1]].prod.a[3]+1);
			t[v].val.a[1]+=std::min(t[t[v].c[1]].prod.a[3],t[t[v].c[1]].prod.a[0]+1);
			t[v].val.a[3]+=std::min(t[t[v].c[1]].prod.a[3],t[t[v].c[1]].prod.a[0]+1);
			t[v].val.a[0]-=std::min(t[w].prod.a[0],t[w].prod.a[3]+1);
			t[v].val.a[2]-=std::min(t[w].prod.a[0],t[w].prod.a[3]+1);
			t[v].val.a[1]-=std::min(t[w].prod.a[3],t[w].prod.a[0]+1);
			t[v].val.a[3]-=std::min(t[w].prod.a[3],t[w].prod.a[0]+1);
			t[v].c[1]=w;
			pushup(v);
		}
	}
	void link(int v,int w){
		access(v);
		splay(v);
		t[v].pa=w;
	}
}lc;

int n;

void initialize(int N_, std::vector<int> A, std::vector<int> B) {
	static int qu[N+1],hd,tl,lv[N+1];
	std::vector<std::vector<int>>g(N+1);

	n=N_;
	for(int i=0;i+1<n;++i) g[A[i]].push_back(B[i]),g[B[i]].push_back(A[i]);
	for(int i=1;i<=n;++i) lv[i]=0;

	qu[tl=0]=hd=1;
	while(hd-tl){
		int u=qu[tl++];
		lv[u]=1;
		for(auto v:g[u])if(lv[v]==0)lv[v]=1,qu[hd++]=v,lc.link(v,u);
	}

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

	g.clear();
}

void ski(int v,int m){
	lc.access(v);
	lc.splay(v);
	if(col[v]==1){
		lc.t[v].val.a[1]+=m*1e8;
		lc.t[v].val.a[3]+=m*1e8;
	}else if(col[v]==2){
		lc.t[v].val.a[0]+=m*1e8;
		lc.t[v].val.a[2]+=m*1e8;
	}else{
	}
	lc.pushup(v);
}

int getans(){
	lc.access(1);
	lc.splay(1);
	lc.t[1].prod.pt();

	Mat z;
	z.a[0]=z.a[1]=z.a[2]=z.a[3]=0;
	z=z*lc.t[1].prod;
	z=lc.t[1].prod;

	return std::min(z.a[0],z.a[3]);//std::min(lc.t[1].prod.a[0],lc.t[1].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();
}

Compilation message (stderr)

catdog.cpp: In member function 'void Mat::pt()':
catdog.cpp:22:30: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   22 |                 printf("  [ %d %d %d %d]\n",a[0],a[1],a[2],a[3]);
      |                             ~^              ~~~~
      |                              |                 |
      |                              int               long long int
      |                             %lld
catdog.cpp:22:33: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
   22 |                 printf("  [ %d %d %d %d]\n",a[0],a[1],a[2],a[3]);
      |                                ~^                ~~~~
      |                                 |                   |
      |                                 int                 long long int
      |                                %lld
catdog.cpp:22:36: warning: format '%d' expects argument of type 'int', but argument 4 has type 'long long int' [-Wformat=]
   22 |                 printf("  [ %d %d %d %d]\n",a[0],a[1],a[2],a[3]);
      |                                   ~^                  ~~~~
      |                                    |                     |
      |                                    int                   long long int
      |                                   %lld
catdog.cpp:22:39: warning: format '%d' expects argument of type 'int', but argument 5 has type 'long long int' [-Wformat=]
   22 |                 printf("  [ %d %d %d %d]\n",a[0],a[1],a[2],a[3]);
      |                                      ~^                    ~~~~
      |                                       |                       |
      |                                       int                     long long int
      |                                      %lld

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