Submission #197056

#	Time	Username	Problem	Language	Result	Execution time	Memory
197056		iefnah06	Cats or Dogs (JOI18_catdog)	C++11	100 / 100	293 ms	27612 KiB

catdog

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

const int MAXN = 1.1e5;
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 heavypar[MAXN];
int num[MAXN];
int pos[MAXN];

void dfs_hld(int cur, int top) {
	heavypar[cur] = top;
	pos[cur] = num[top];
	num[top]++;
	bool isfirst = true;
	for (int nxt : adj[cur]) {
		dfs_hld(nxt, (isfirst ? top : nxt));
		isfirst = 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.a10);
		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 < s; i++) {
			cost[i+s].a01 = cost[i+s].a10 = 1;
		}
		for (int i = s-1; i; i--) {
			cost[i] = cost[2*i] * cost[2*i+1];
		}
	}

	void update(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 n, std::vector<int> a, std::vector<int> b) {
	N = n;
	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) == (heavypar[i] == i));
		if (heavypar[i] == i) {
			seg[i] = segtree(num[i]);
		}
	}
}

void update(int cur, int v0, int v1) {
	while (cur) {
		int top = heavypar[cur];
		int cur0, cur1, nxt0, nxt1;
		seg[top].eval(cur0, cur1);
		seg[top].update(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 query();
 
int cat(int v) {
	A[v] = 1;
	update(v, 0, N);
	return query();
}
 
int dog(int v) {
	A[v] = 2;
	update(v, N, 0);
	return query();
}
 
int neighbor(int v) {
	if (A[v] == 1) {
		update(v, 0, -N);
	} else if (A[v] == 2) {
		update(v, -N, 0);
	} else assert(false);
	A[v] = 0;
	return query();
}

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

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