Submission #111690

#	Time	Username	Problem	Language	Result	Execution time	Memory
111690		gs14004	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	1681 ms	28904 KiB

catdog

#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int MAXT = 270000;
const int inf = 1e9;

int n, a[MAXN];
vector<int> gph[MAXN];
int sz[MAXN], chn[MAXN], csz[MAXN], dfn[MAXN], par[MAXN], piv;

int slack[MAXN][3];

struct mtrx{
	int a[3][3];
}E;

mtrx mul(mtrx a, mtrx b){
	mtrx c; memset(c.a, 0x3f, sizeof(c.a));
	for(int i=0; i<3; i++){
		for(int j=0; j<3; j++){
			for(int k=0; k<3; k++){
				c.a[j][k] = min(a.a[j][i] + b.a[i][k], c.a[j][k]);
			}
		}
	}
	return c;
}

struct seg{
	int lim;
	mtrx tree[MAXT];
	void init(int n){
		for(lim = 1; lim <= n; lim <<= 1);
		for(int i=0; i<MAXT; i++){
			tree[i] = E;
		}
	}
	void add(int x, mtrx v){
		x += lim;
		tree[x] = v;
		while(x > 1){
			x >>= 1;
			tree[x] = mul(tree[2*x], tree[2*x+1]);
		}
	}
	mtrx query(int s, int e){
		s += lim;
		e += lim;
		mtrx lmtrx = E, rmtrx = E;
		while(s < e){
			if(s%2 == 1) lmtrx = mul(lmtrx, tree[s++]); 
			if(e%2 == 0) rmtrx = mul(tree[e--], rmtrx);
			s >>= 1;
			e >>= 1;
		}
		if(s == e) rmtrx = mul(tree[s], rmtrx);
		return mul(lmtrx, rmtrx);
	}	
}seg;

vector<int> line_query(int s, int e){
	auto quer = seg.query(s, e);
	vector<int> nxt(3);
	for(int i=0; i<3; i++){
		nxt[i]  = 1e9;
		for(int j=0; j<3; j++) nxt[i] = min(nxt[i], quer.a[i][j]);
	}
	return nxt;
}

void slack_update(int v){
	mtrx m;
	m.a[0][0] = slack[v][0] + (a[v] ? inf : 0);
	m.a[0][1] = slack[v][1] + 1 + (a[v] == 2 ? inf : 0);
	m.a[0][2] = slack[v][2] + 1 + (a[v] == 1 ? inf : 0);

	m.a[1][0] = slack[v][0] + (a[v] ? inf : 0);
	m.a[1][1] = slack[v][1] + 0 + (a[v] == 2 ? inf : 0);
	m.a[1][2] = slack[v][2] + 1 + (a[v] == 1 ? inf : 0);

	m.a[2][0] = slack[v][0] + (a[v] ? inf : 0);
	m.a[2][1] = slack[v][1] + 1 + (a[v] == 2 ? inf : 0);
	m.a[2][2] = slack[v][2] + 0 + (a[v] == 1 ? inf : 0);

	seg.add(v, m);
}

void Do(int v, int w){
	vector<int> pth;
	for(int i = v; i; i = par[chn[i]]){
		pth.push_back(i);
	}
	reverse(pth.begin(), pth.end());
	for(auto &i : pth){
		auto queryV = line_query(dfn[chn[i]], dfn[chn[i]] + csz[chn[i]] - 1);
		int parV = par[chn[i]];
		parV = dfn[parV];
		slack[parV][0] -= queryV[0];
		slack[parV][1] -= queryV[1];
		slack[parV][2] -= queryV[2];
		if(parV) slack_update(parV);
	}
	a[dfn[v]] = w;
	slack_update(dfn[v]);
	reverse(pth.begin(), pth.end());
	for(auto &i : pth){
		auto queryV = line_query(dfn[chn[i]], dfn[chn[i]] + csz[chn[i]] - 1);
		int parV = par[chn[i]];
		parV = dfn[parV];
		slack[parV][0] += queryV[0];
		slack[parV][1] += queryV[1];
		slack[parV][2] += queryV[2];
		if(parV) slack_update(parV);
	}
}

int cat(int v) {
	Do(v, 1);
	return *min_element(slack[0], slack[0] + 3);
}

int dog(int v) {
	Do(v, 2);
	return *min_element(slack[0], slack[0] + 3);
}

int neighbor(int v) {
	Do(v, 0);
	return *min_element(slack[0], slack[0] + 3);
}

void dfs(int x){
	sz[x] = 1;
	for(auto &i : gph[x]){
		gph[i].erase(find(gph[i].begin(), gph[i].end(), x));
		par[i] = x;
		dfs(i);
		sz[x] += sz[i];
	}
	sort(gph[x].begin(), gph[x].end(), [&](const int &a, const int &b){
		return sz[a] > sz[b];
	});
}

void hld(int x){
	dfn[x] = ++piv;
	csz[chn[x]]++;
	if(gph[x].empty()) return;
	chn[gph[x][0]] = chn[x];
	hld(gph[x][0]);
	for(int i=1; i<gph[x].size(); i++){
		chn[gph[x][i]] = gph[x][i];
		hld(gph[x][i]);
	}
}

void initialize(int N, std::vector<int> A, std::vector<int> B) {
	n = N;
	for(int i=0; i<n-1; i++){
		gph[A[i]].push_back(B[i]);
		gph[B[i]].push_back(A[i]);
	}
	dfs(1);
	chn[1] = 1;
	hld(1);
	for(int i=0; i<3; i++){
		for(int j=0; j<3; j++){
			E.a[i][j] = (i == j ? 0 : 1e9);
		}
	}
	seg.init(n);
}

Compilation message (stderr)

catdog.cpp: In function 'void hld(int)':
catdog.cpp:152:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<gph[x].size(); i++){
               ~^~~~~~~~~~~~~~

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