Submission #388429

#	Time	Username	Problem	Language	Result	Execution time	Memory
388429		pure_mem	Cats or Dogs (JOI18_catdog)	C++14	100 / 100	1101 ms	24764 KiB

catdog

#include "catdog.h"
#include <bits/stdc++.h>

#define X first
#define Y second
#define MP make_pair

using namespace std;

const int MAXN = 1e5 + 12;

struct node{
	bool trash = 0;
	int	t[2][2] = {{MAXN, MAXN}, {MAXN, MAXN}};
}t[MAXN * 4];

node merge(const node &x, const node &y){
	if(x.trash)
		return y;
	else if(y.trash)
		return x;
	node tmp;
	for(int i1 = 0;i1 < 2;i1++){
		for(int j1 = 0;j1 < 2;j1++){
			for(int i2 = 0;i2 < 2;i2++){
				for(int j2 = 0;j2 < 2;j2++){
					tmp.t[i1][j2] = min(tmp.t[i1][j2], x.t[i1][j1] + (j1 != i2) + y.t[i2][j2]);
				}
			}
		}
	}
	return tmp;
}

int n, sz[MAXN], parent[MAXN], cl[MAXN];
int hldPtr, hldCnt, hld[MAXN], hldSt[MAXN], hldFin[MAXN], hldCmp[MAXN], hldId[MAXN];
vector< int > graph[MAXN];
pair< int, int > dp[MAXN];

void build(int v, int tl, int tr){
	if(tl == tr){
		t[v].t[0][0] = t[v].t[1][1] = 0;
		return;
	}
	int tm = (tl + tr) / 2;
	build(v * 2, tl, tm);
	build(v * 2 + 1, tm + 1, tr);
	t[v] = merge(t[v * 2], t[v * 2 + 1]);
}

void upd(int v, int tl, int tr, int pos){
	if(tl > pos || pos > tr)
		return;
	if(tl == tr){
		t[v].t[0][0] = t[v].t[1][1] = MAXN;
		if(cl[hld[tl]] != 2)
			t[v].t[0][0] = dp[hld[tl]].X;
		if(cl[hld[tl]] != 1)
			t[v].t[1][1] = dp[hld[tl]].Y;
		return;
	}
	int tm = (tl + tr) / 2;
	upd(v * 2, tl, tm, pos);
	upd(v * 2 + 1, tm + 1, tr, pos);
	t[v] = merge(t[v * 2], t[v * 2 + 1]);    
}

node get(int v, int tl, int tr, int l, int r){
	if(tl > r || l > tr)
		return t[0];
	if(tl >= l && tr <= r)
		return t[v];
	int tm = (tl + tr) / 2;
	return merge(get(v * 2, tl, tm, l, r), get(v * 2 + 1, tm + 1, tr, l, r));
}

void dfs_sz(int v, int pr){
	sz[v] = 1, parent[v] = pr;
	for(int to: graph[v]){
		if(to != pr){
			dfs_sz(to, v);
			sz[v] += sz[to];
		}
	}
}

void dfs(int v, int pr){
	hldPtr++;
	hld[hldPtr] = v, hldId[v] = hldPtr, hldCmp[v] = hldCnt;
	if(hldSt[hldCnt] == 0)
		hldSt[hldCnt] = v;
	int mx = 0;
	for(int to: graph[v]){
		if(to != pr && sz[mx] < sz[to])
			mx = to;
	}
	if(mx)
		dfs(mx, v);
	else
		hldFin[hldCnt] = v;
	for(int to: graph[v]){
		if(to != pr && to != mx)
			hldCnt++, dfs(to, v);
	}
} 

void initialize(int N, vector<int> A, vector<int> B) {
	n = N, t[0].trash = 1;
	for(int i = 0;i < n - 1;i++){
		graph[A[i]].push_back(B[i]);
		graph[B[i]].push_back(A[i]);
	}
	dfs_sz(1, -1);
	dfs(1, 1);
	build(1, 1, n);
}
   
int solve(int v, int _cl){
	int tmpV = v;
	while(v != -1){
		int vSt = hldSt[hldCmp[v]], vFin = hldFin[hldCmp[v]];
		node tmp = get(1, 1, n, hldId[vSt], hldId[vFin]);
		if(vSt != 1){
			dp[parent[vSt]].X -= min(min(tmp.t[0][0], tmp.t[0][1]), min(tmp.t[1][0], tmp.t[1][1]) + 1);
			dp[parent[vSt]].Y -= min(min(tmp.t[0][0], tmp.t[0][1]) + 1, min(tmp.t[1][0], tmp.t[1][1]));
		}
		v = parent[vSt];	
	}	
	v = tmpV, cl[v] = _cl;
	while(v != -1){
		int vSt = hldSt[hldCmp[v]], vFin = hldFin[hldCmp[v]];
		upd(1, 1, n, hldId[v]);
		node tmp = get(1, 1, n, hldId[vSt], hldId[vFin]);
		if(vSt != 1){
			dp[parent[vSt]].X += min(min(tmp.t[0][0], tmp.t[0][1]), min(tmp.t[1][0], tmp.t[1][1]) + 1);
			dp[parent[vSt]].Y += min(min(tmp.t[0][0], tmp.t[0][1]) + 1, min(tmp.t[1][0], tmp.t[1][1]));
		}
		else{
			return min(min(tmp.t[0][0], tmp.t[0][1]), min(tmp.t[1][0], tmp.t[1][1]));
		}
		v = parent[vSt];
	}
}

int cat(int v) {
  return solve(v, 1);
}

int dog(int v) {
  return solve(v, 2);
}

int neighbor(int v) {
  return solve(v, 3);
}

Compilation message (stderr)

catdog.cpp: In function 'int solve(int, int)':
catdog.cpp:143:1: warning: control reaches end of non-void function [-Wreturn-type]
  143 | }
      | ^

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