Submission #592433

#	Time	Username	Problem	Language	Result	Execution time	Memory
592433		Bobaa	Cats or Dogs (JOI18_catdog)	C++17	0 / 100	4 ms	5792 KiB

catdog

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

const int maxn = 1e5 + 5; 
int n;
vector<int> adj[maxn]; 
int A[maxn]; 
int sz[maxn]; 
int par[maxn]; 

void dfs_sz(int cur, int prv) {
	if (prv) adj[cur].erase(find(adj[cur].begin(), adj[cur].end(), prv)); 
	sz[cur] = 1; 
	par[cur] = prv; 
	for (int nxt : adj[cur]) {
		dfs_sz(nxt, cur); 
		sz[cur] += sz[nxt]; 
	}
	nth_element(adj[cur].begin(), adj[cur].begin(), adj[cur].end(), [&](int i, int j) {
		return sz[i] > sz[j]; 
	}); 
}

int hvypar[maxn]; 
int num[maxn]; 
int pos[maxn]; 

void dfs_hld(int cur, int top) {
	hvypar[cur] = top; 
	pos[cur] = num[top]; 
	num[top]++; 
	bool isfrst = true; 
	for (int nxt : adj[cur]) {
		dfs_hld(nxt, (isfrst ? top : nxt)); 
		isfrst = false; 
	}
}

struct mat {
	int a00, a01, a10, a11; 
	friend mat operator * (const mat& a, const mat& b) {
		mat r; 
		r.a00 = min(a.a00 + b.a00, a.a01 + b.a01); 
		r.a01 = min(a.a00 + b.a01, a.a01 + b.a11); 
		r.a10 = min(a.a10 + b.a00, a.a11 + b.a10); 
		r.a11 = min(a.a10 + b.a01, a.a11 + b.a11); 
		return r; 
	}
};

struct segtree {
	int s; 
	vector<mat> cost; 
	
	segtree() {}
	
	segtree(int n) {
		for (s = 1; s < n; s *= 2) {}
		cost = vector<mat>(2 * s); 
		for (int i = 0; i < 2 * s; i++) cost[i].a01 = cost[i].a10 = 1; 
	}
	
	void upd(int i, int& v0, int& v1) {
		i += s; 
		cost[i].a00 += v0; 
		cost[i].a01 += v0; 
		cost[i].a10 += v1; 
		cost[i].a11 += v1; 
		for (i /= 2; i; i /= 2) cost[i] = cost[2 * i] * cost[2 * i + 1]; 
	}
	
	void eval(int& a0, int& a1) {
		a0 = min(cost[1].a00, cost[1].a01); 
		a1 = min(cost[1].a10, cost[1].a11); 
	}
} seg[maxn]; 

void initialize(int k, vector<int> a, vector<int> b) {
	n = k; 
	for (int i = 0; i < n - 1; i++) {
		adj[a[i]].push_back(b[i]); 
		adj[b[i]].push_back(a[i]); 
	}
	for (int i = 1; i <= n; i++) A[i] = 0; 
	dfs_sz(1, 0); 
	dfs_hld(1, 1); 
	for (int i = 1; i <= n; i++) {
		assert((pos[i] == 0) == (hvypar[i] == i)); 
		if (hvypar[i] == i) seg[i] = segtree(num[i]); 
	}
}

void upd(int cur, int v0, int v1) {
	while (cur) {
		int top = hvypar[cur]; 
		int cur0, cur1, nxt0, nxt1; 
		seg[top].eval(cur0, cur1); 
		seg[top].upd(pos[cur], v0, v1); 
		seg[top].eval(nxt0, nxt1); 
		v0 = min(nxt0, nxt1 + 1) - min(cur0, cur1 + 1); 
		v1 = min(nxt0 + 1, nxt1) - min(cur0 + 1, cur1); 
		cur = par[top]; 
	}
}

int qry() {
	int a0, a1;
	seg[1].eval(a0, a1);
	return min(a0, a1);
}

int cat(int v) {
	A[v] = 1;
	upd(v, 0, n);
	return qry();
}
 
int dog(int v) {
	A[v] = 2;
	upd(v, n, 0);
	return qry();
}
 
int neighbor(int v) {
	if (A[v] == 1) upd(v, 0, -n);
	else if (A[v] == 2) upd(v, -n, 0);
	else assert(false);
	A[v] = 0;
	return qry();
}

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