Submission #835208

#	Time	Username	Problem	Language	Result	Execution time	Memory
835208		qwerasdfzxcl	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	242 ms	36120 KiB

catdog

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

using namespace std;
typedef long long ll;

constexpr int INF1 = 1e9 + 100;
constexpr ll INF2 = 4e18;

int n;
vector<int> adj[100100], G[100100];
int par[100100], sz[100100], in[100100], top[100100], leaf[100100], typ[100100], cnt;
array<ll, 2> A[100100], C[100100], D[100100];

void operator += (array<ll, 2> &L, const array<ll, 2> &R){
	L[0] += R[0], L[1] += R[1];
}

void operator -= (array<ll, 2> &L, const array<ll, 2> &R){
	L[0] -= R[0], L[1] -= R[1];
}

struct M{
	ll a[2][2];

	M(){}
	M(ll _x, ll _y, ll _z, ll _w){
		a[0][0] = _x;
		a[0][1] = _y;
		a[1][0] = _z;
		a[1][1] = _w;
	}

	array<ll, 2> calc(const array<ll, 2> &x) const{
		return {min(x[0]+a[0][0], x[1]+a[1][0]), min(x[0]+a[0][1], x[1]+a[1][1])};
	}

	M operator + (const M &F) const{
		M ret(INF2, INF2, INF2, INF2);
		for (int i=0;i<2;i++){
			for (int j=0;j<2;j++){
				for (int k=0;k<2;k++) ret.a[i][k] = min(ret.a[i][k], a[j][k] + F.a[i][j]);
			}
		}

		return ret;
	}
};

struct Seg{
	M tree[200200];
	int sz;

	void init(int n){
		sz = n;
		for (int i=sz;i<sz*2;i++) tree[i] = M(0, 1, 1, 0);
		for (int i=sz-1;i;i--) tree[i] = tree[i<<1] + tree[i<<1|1];
	}

	void update(int p, const array<ll, 2> &x){
		p += sz;
		tree[p] = M(x[0], x[1]+1, x[0]+1, x[1]);
		for (p>>=1;p;p>>=1) tree[p] = tree[p<<1] + tree[p<<1|1];
	}

	M query(int l, int r){
		// printf("query %d %d\n", l, r);
		++r;
		M retL(0, INF2, INF2, 0), retR(0, INF2, INF2, 0);
		for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
			if (l&1) retL = retL + tree[l++];
			if (r&1) retR = tree[--r] + retR;
		}

		// printf("(%lld, %lld, %lld, %lld)\n", retL.a[0][0], retL.a[0][1], retL.a[1][0], retL.a[1][1]);
		// printf("(%lld, %lld, %lld, %lld)\n", retR.a[0][0], retR.a[0][1], retR.a[1][0], retR.a[1][1]);
		// auto ret = retL + retR;
		// printf("(%lld, %lld, %lld, %lld)\n", ret.a[0][0], ret.a[0][1], ret.a[1][0], ret.a[1][1]);

		return retL + retR;
	}
}tree;

void dfs0(int s, int pa = 0){
	par[s] = pa;
	sz[s] = 1;

	for (auto &v:adj[s]) if (v!=pa){
		G[s].push_back(v);
		dfs0(v, s);
		sz[s] += sz[v];
	}
}

void dfs1(int s){
	in[s] = ++cnt;
	if (G[s].empty()){
		leaf[top[s]] = s;
		return;
	} 

	swap(G[s][0], *max_element(G[s].begin(), G[s].end(), [&](int x, int y){return sz[x] < sz[y];}));

	for (auto &v:G[s]){
		if (v==G[s][0]) top[v] = top[s];
		else top[v] = v;

		dfs1(v);
	}
}

void initialize(int N, std::vector<int> A, std::vector<int> B) {
	n = N;
	cnt = 0;
	for (int i=0;i<N-1;i++){
		adj[A[i]].push_back(B[i]);
		adj[B[i]].push_back(A[i]);
	}

	top[1] = 1;
	dfs0(1);
	dfs1(1);

	fill(::A+1, ::A+n+1, array<ll, 2>{0, 0});
	fill(C+1, C+n+1, array<ll, 2>{0, 0});
	fill(D+1, D+n+1, array<ll, 2>{0, 0});
	fill(typ+1, typ+n+1, 0);
	tree.init(n+1);

	// printf("ok\n");
}

void update(int x){
	C[x] -= A[x];
	if (typ[x]==0) A[x] = {0, 0};
	else if (typ[x]==1) A[x] = {0, INF1};
	else A[x] = {INF1, 0};
	C[x] += A[x];

	tree.update(in[x], C[x]);

	while(true){
		x = top[x];
		if (x!=1) C[par[x]] -= array<ll, 2>{min(D[x][0], D[x][1]+1), min(D[x][0]+1, D[x][1])};
		D[x] = tree.query(in[x], in[leaf[x]]).calc({0, 0});
		if (x!=1) C[par[x]] += array<ll, 2>{min(D[x][0], D[x][1]+1), min(D[x][0]+1, D[x][1])};
		else break;

		x = par[x];
		tree.update(in[x], C[x]);
	}

	// printf("ok done ans = %lld\n", min(D[1][0], D[1][1]));
	// printf("top: ");
	// for (int i=1;i<=n;i++) printf("%d ", top[i]);
	// printf("\n");

	// printf("A: ");
	// for (int i=1;i<=n;i++) printf("(%lld, %lld) ", A[i][0], A[i][1]);
	// printf("\n");

	// printf("C: ");
	// for (int i=1;i<=n;i++) printf("(%lld, %lld) ", C[i][0], C[i][1]);
	// printf("\n");

	// printf("D: ");
	// for (int i=1;i<=n;i++) printf("(%lld, %lld) ", D[i][0], D[i][1]);
	// printf("\n");
}

int cat(int v) {
	typ[v] = 1;
	update(v);
	return min(D[1][0], D[1][1]);
}

int dog(int v) {
	typ[v] = 2;
	update(v);
	return min(D[1][0], D[1][1]);
}

int neighbor(int v) {
	typ[v] = 0;
	update(v);
	return min(D[1][0], D[1][1]);
}

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