Submission #134140

#	Time	Username	Problem	Language	Result	Execution time	Memory
134140		ainta	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	362 ms	38140 KiB

catdog

#include "catdog.h"
#include<vector>
#include<algorithm>
#define N_ 101000
#define pii pair<int,int>
using namespace std;

int w[N_], n, par[N_], C[N_], HL[N_][2], INF = 1e9;
vector<int>E[N_], Ch[N_];

struct Mat {
	int A[2][2];
	Mat() {
		for (int i = 0; i < 2; i++)for (int j = 0; j < 2; j++)A[i][j] = 0;
	}
};
Mat Merge(Mat a, Mat b) {
	int i, k, j;
	Mat T;
	for (i = 0; i < 2; i++)for (j = 0; j < 2; j++)T.A[i][j] = INF;
	for (i = 0; i < 2; i++) for (k = 0; k < 2; k++) for (j = 0; j < 2; j++) T.A[i][j] = min(T.A[i][j], a.A[i][k] + b.A[k][j]);
	return T;
}

struct Tree {
	vector<int>V;
	vector<Mat>IT;
	vector<pii>U;
	int n, sz;
	void UDT(int nd) {
		IT[nd] = Merge(IT[nd * 2], IT[nd * 2 + 1]);
	}
	void init(int nd, int b, int e) {
		if (b == e) {
			IT[nd].A[0][0] = IT[nd].A[1][1] = 0;
			IT[nd].A[0][1] = IT[nd].A[1][0] = 1;
			return;
		}
		int m = (b + e) >> 1;
		init(nd * 2, b, m);
		init(nd * 2 + 1, m + 1, e);
		UDT(nd);
	}
	void init() {
		if (V.empty())return;
		n = V.size();
		U.resize(n);
		sz = 1;
		while (sz <= n)sz *= 2;
		IT.resize(sz * 2);
		init(1, 0, n - 1);
	}
	void Put(int nd, int b, int e, int x, int cur) {
		if (b == e) {
			IT[nd].A[0][0] = U[b].first;
			IT[nd].A[1][1] = U[b].second;
			IT[nd].A[0][1] = U[b].first + 1;
			IT[nd].A[1][0] = U[b].second + 1;
			if (cur == 1) IT[nd].A[1][0] = IT[nd].A[1][1] = INF;
			if (cur == 2) IT[nd].A[0][0] = IT[nd].A[0][1] = INF;
			return;
		}
		int m = (b + e) >> 1;
		if (x <= m)Put(nd * 2, b, m, x, cur);
		else Put(nd * 2 + 1, m + 1, e, x, cur);
		UDT(nd);
	}
	pii Get() {
		return { min(IT[1].A[0][0],IT[1].A[1][0]), min(IT[1].A[0][1], IT[1].A[1][1]) };
	}
	void Put(int x, int cur) {
		Put(1, 0, n - 1, x, cur);
	}
}T[N_];

void DFS(int a, int pp) {
	par[a] = pp;
	C[a] = 1;
	for (auto &x : E[a]) {
		if (x == pp)continue;
		DFS(x, a);

		Ch[a].push_back(x);
		C[a] += C[x];
	}
}

void HLD(int a, int ppp) {
	T[ppp].V.push_back(a);
	int pv = -1, Mx = -1;
	for (auto &x : Ch[a]) {
		if (Mx < C[x]) {
			Mx = C[x];
			pv = x;
		}
	}
	if (pv == -1)return;
	HLD(pv, ppp);
	for (auto &x : Ch[a]) {
		if(x!=pv)HLD(x, x);
	}
}

void initialize(int N, std::vector<int> A, std::vector<int> B) {
	n = N;
	int i;
	for (i = 0; i < n - 1; i++) {
		E[A[i]].push_back(B[i]);
		E[B[i]].push_back(A[i]);
	}
	DFS(1, 0);
	HLD(1, 1);
	for (i = 1; i <= n; i++) {
		if (T[i].V.empty())continue;
		reverse(T[i].V.begin(), T[i].V.end());
		for (int j = 0; j < T[i].V.size(); j++) {
			int a = T[i].V[j];
			HL[a][0] = i, HL[a][1] = j;
		}
		T[i].init();
	}
}

void Add(int v, pii bef, pii aft) {
	int fi = aft.first - bef.first;
	int se = aft.second - bef.second;
	int a = HL[v][0], b = HL[v][1];
	T[a].U[b].first += fi;
	T[a].U[b].second += se;
}

int Go(int v, int ck) {
	int a = HL[v][0], b = HL[v][1];
	w[v] = ck;
	while (1) {
		pii bef = T[a].Get();
		T[a].Put(b, ck);
		pii aft = T[a].Get();
		int pp = par[a];
		if (!pp)break;
		Add(pp, bef, aft);
		a = HL[pp][0], b = HL[pp][1];
		ck = w[pp];
	}
	pii z = T[1].Get();
	return min(z.first, z.second);
}

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

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

int neighbor(int v) {
	return Go(v, 0);
}

Compilation message (stderr)

catdog.cpp: In function 'void initialize(int, std::vector<int>, std::vector<int>)':
catdog.cpp:116:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < T[i].V.size(); j++) {
                   ~~^~~~~~~~~~~~~~~

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