Submission #102479

#	Time	Username	Problem	Language	Result	Execution time	Memory
102479		Dat160601	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	441 ms	31864 KiB

catdog

#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;

#define mp make_pair
#define pb push_back
#define fi first
#define se second

const int N = 1e5 + 7, inf = 1e6;

int n, par[N], head[N], chain[N], pos[N], sz[N], st[N];
vector <int> edge[N];

struct node{
	int dp[2][2];
	node(){
		dp[0][0] = dp[1][1] = 0;
		dp[0][1] = dp[1][0] = inf;
	}
};

node merge(node a, node b){
	node ret;
	for(int i = 0; i <= 1; i++){
		for(int j = 0; j <= 1; j++){
			ret.dp[i][j] = inf;
			for(int k = 0; k <= 1; k++){
				for(int l = 0; l <= 1; l++){
					ret.dp[i][j] = min(ret.dp[i][j], a.dp[i][k] + b.dp[l][j] + (k ^ l));
				}
			}
		}
	}
	return ret;
}

struct segtree{
	vector <node> it;
	int sz;

	void init(int k, int l, int r){
		if(l == r) return;
		int mid = (l + r) >> 1;
		init(k << 1, l, mid);
		init(k << 1 | 1, mid + 1, r);
		it[k] = merge(it[k << 1], it[k << 1 | 1]);
	}

	void init(int pos){
		sz = pos;
		it.resize(4 * sz + 5);
		init(1, 1, sz);
	}

	void update(int k, int l, int r, int pos, int v0, int v1){
		if(l > pos || r < pos) return;
		if(l == r){
			it[k].dp[0][0] += v0;
			it[k].dp[1][1] += v1;
			return;
		}
		int mid = (l + r) >> 1;
		update(k << 1, l, mid, pos, v0, v1);
		update(k << 1 | 1, mid + 1, r, pos, v0, v1);
		it[k] = merge(it[k << 1], it[k << 1 | 1]);
	}

	void update(int pos, int v0, int v1){
		update(1, 1, sz, pos, v0, v1);
	}

	pair <int, int> get(){
		int f1 = min(it[1].dp[0][0], it[1].dp[0][1]);
		int f2 = min(it[1].dp[1][0], it[1].dp[1][1]);
		return mp(min(f1, f2 + 1), min(f1 + 1, f2));
	}
} tree[N];

void dfs(int u, int p){
	sz[u] = 1;
	for(int v : edge[u]){
		if(v == p) continue;
		par[v] = u;
		dfs(v, u);
		sz[u] += sz[v];
	}
}

void hld(int u, int p){
	int nxt = -1;
	for(int v : edge[u]){
		if(v == p) continue;
		if(nxt < 0 || sz[nxt] < sz[v]){
			nxt = v;
		}
	}
	if(nxt < 0){
		tree[chain[u]].init(pos[u]);
		return;
	}
	chain[nxt] = chain[u];
	pos[nxt] = pos[u] + 1;
	hld(nxt, u);
	for(int v : edge[u]){
		if(v == p || v == nxt) continue;
		chain[v] = v;
		head[v] = v;
		pos[v] = 1;
		hld(v, u);
	}
}

void initialize(int p, vector <int> A, vector <int> B){
	n = p;
	for(int i = 0; i < n - 1; i++){
		edge[A[i]].pb(B[i]);
		edge[B[i]].pb(A[i]);
	}
	dfs(1, 1);
	head[1] = 1, chain[1] = 1, pos[1] = 1;
	hld(1, 1);
}

void solve(int u, int v0, int v1){
	while(u){
		int cur = chain[u];
		//cout << cur << endl;
		int pv0, pv1;
		pair <int, int> now = tree[cur].get();
		pv0 = now.fi, pv1 = now.se;
		tree[cur].update(pos[u], v0, v1);
		now = tree[cur].get();
		v0 = now.fi - pv0, v1 = now.se - pv1;
		u = head[cur];
		u = par[u];
	}
}

int getans(){
	return min(min(tree[1].it[1].dp[0][0], tree[1].it[1].dp[0][1]), min(tree[1].it[1].dp[1][0], tree[1].it[1].dp[1][1]));
}

int cat(int v) {
	st[v] = 1;
	solve(v, 0, inf);
	return getans();
}

int dog(int v) {
	st[v] = 2;
	solve(v, inf, 0);
	return getans();
}

int neighbor(int v){
	if(st[v] == 0) return getans();
	if(st[v] == 1) solve(v, 0, -inf);
	if(st[v] == 2) solve(v, -inf, 0);
	st[v] = 0;
	return getans();
}

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