제출 #153765

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
153765		tutis	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	1677 ms	27896 KiB

catdog

#include <bits/stdc++.h>
using namespace std;
const int maxn = 101010;
vector<int>adj[maxn];
int pa[maxn];
int dfs(int i, int p)
{
	pa[i] = p;
	int sz = 1;
	pair<int, int>mx = {0, 0};
	for (int t = 0; t < (int)adj[i].size(); t++)
	{
		int j = adj[i][t];
		if (j == p)
			continue;
		int x = dfs(j, i);
		sz += x;
		mx = max(mx, {x, t});
	}
	swap(adj[i][0], adj[i][mx.second]);
	return sz;
}
int timer = 1;
int nr[maxn], head[maxn], tail[maxn];
void hld(int i, int p, int h)
{
	nr[i] = timer++;
	head[i] = h;
	tail[h] = i;
	for (int t = 0; t < (int)adj[i].size(); t++)
	{
		int j = adj[i][t];
		if (j != p)
			hld(j, i, t == 0 ? h : j);
	}
}
struct line
{
	int cc = 0, cd = maxn, dd = 0, dc = maxn;
	line() {}
	int mn(int c)
	{
		if (c)
			return min({cd, cc, dc + 1, dd + 1});
		else
			return min({cd + 1, cc + 1, dc, dd});
	}
};
line merge(line a, line b)
{
	line c;
	c.cc = min({a.cc + b.cc, a.cc + b.dc + 1, a.cd + b.cc + 1, a.cd + b.dc});
	c.cd = min({a.cc + b.cd, a.cc + b.dd + 1, a.cd + b.cd + 1, a.cd + b.dd});
	c.dd = min({a.dc + b.cd, a.dc + b.dd + 1, a.dd + b.cd + 1, a.dd + b.dd});
	c.dc = min({a.dc + b.cc, a.dc + b.dc + 1, a.dd + b.cc + 1, a.dd + b.dc});
	return c;
}
struct ST
{
	line X;
	int l, r;
	ST *left, *right;
	ST(int l, int r): l(l), r(r)
	{
		if (l < r)
		{
			left = new ST(l, (l + r) / 2);
			right = new ST((l + r) / 2 + 1, r);
			X = merge(left->X, right->X);
		}
	}
	line get(int x, int y)
	{
		if (x <= l && r <= y)
			return X;
		if (r < x || y < l)
			return line();
		return merge(left->get(x, y), right->get(x, y));
	}
	void set(int x, int w, int c)
	{
		if (l == r)
		{
			if (c)
				X.cc = w;
			else
				X.dd = w;
		}
		else
		{
			if (x <= (l + r) / 2)
				left->set(x, w, c);
			else
				right->set(x, w, c);
			X = merge(left->X, right->X);
		}
	}
} medis(0, 101010);
void initialize(int N, vector<int> A, vector<int> B)
{
	for (int i = 0; i < N - 1; i++)
	{
		adj[A[i]].push_back(B[i]);
		adj[B[i]].push_back(A[i]);
	}
	dfs(1, 0);
	hld(1, 0, 1);
}
int C[maxn], D[maxn], V[maxn];
int fix(int v, int p)
{
	V[v] = p;
	while (true)
	{
		int w = head[v];
		line X = medis.get(nr[w], nr[tail[w]]);
		C[pa[w]] -= X.mn(1);
		D[pa[w]] -= X.mn(0);
		medis.set(nr[v], V[v] == 1 ? maxn : C[v], 1);
		medis.set(nr[v], V[v] == -1 ? maxn : D[v], 0);
		X = medis.get(nr[w], nr[tail[w]]);
		C[pa[w]] += X.mn(1);
		D[pa[w]] += X.mn(0);
		if (v == 1)break;
		if (v != w)
			v = w;
		else
			v = pa[v];
	}
	return min(C[0], D[0]);
}
int cat(int v)
{
	return fix(v, -1);
}
int dog(int v)
{
	return fix(v, 1);
}
int neighbor(int v)
{
	return fix(v, 0);
}

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