Submission #153756

#	Time	Username	Problem	Language	Result	Execution time	Memory
153756		tutis	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	2245 ms	38392 KiB

catdog

/*input
3
1 2 1
2 3 1
3 1 2
*/
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
vector<ll>adj[101010];
ll pa[101010], sz[101010];
void dfs(ll i, ll p)
{
	if (p != 0)
		adj[i].erase(find(adj[i].begin(), adj[i].end(), p));
	pa[i] = p;
	sz[i] = 1;
	pair<ll, ll>mx = { -1, -1};
	for (ll t = 0; t < (ll)adj[i].size(); t++)
	{
		ll j = adj[i][t];
		dfs(j, i);
		sz[i] += sz[j];
		mx = max(mx, {sz[j], t});
	}
	if (mx.second != -1)
		swap(adj[i][0], adj[i][mx.second]);
}
ll timer = 1;
ll nr[101010], head[101010], tail[101010];
void hld(ll i, ll h)
{
	nr[i] = timer++;
	head[i] = h;
	tail[h] = i;
	for (ll t = 0; t < (ll)adj[i].size(); t++)
	{
		ll j = adj[i][t];
		hld(j, t == 0 ? h : j);
	}
}
struct line
{
	ll cc = 0, cd = 0, dd = 0, dc = 0;
	line() {}
	line(string s) {cc = -1; cd = -1; dd = -1; dc = -1;}
};
line merge(line a, line b)
{
	if (a.cc < 0)
		return b;
	if (b.cc < 0)
		return a;
	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;
	ll l, r;
	ST *left, *right;
	ST(ll l, ll 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);
		}
		else
		{
			X.cc = 0;
			X.cd = 101010;
			X.dc = 101010;
			X.dd = 0;
		}
	}
	line get(ll x, ll y)
	{
		if (x <= l && r <= y)
			return X;
		if (r < x || y < l)
			return line("blogai");
		return merge(left->get(x, y), right->get(x, y));
	}
	void setC(ll x, ll w)
	{
		if (l == r)
		{
			X.cc = w;
		}
		else
		{
			if (x <= (l + r) / 2)
				left->setC(x, w);
			else
				right->setC(x, w);
			X = merge(left->X, right->X);
		}
	}
	void setD(ll x, ll w)
	{
		if (l == r)
		{
			X.dd = w;
		}
		else
		{
			if (x <= (l + r) / 2)
				left->setD(x, w);
			else
				right->setD(x, w);
			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, 1);
}
ll C[101010], D[101010], V[101010];
void fix(ll v)
{
	ll w = head[v];
	line X = medis.get(nr[w], nr[tail[w]]);
	C[pa[w]] -= min({X.cd, X.cc, X.dc + 1, X.dd + 1});
	D[pa[w]] -= min({X.cd + 1, X.cc + 1, X.dc, X.dd});
	if (V[v] == -1)
	{
		medis.setC(nr[v], C[v]);
		medis.setD(nr[v], 101010);
	} else if (V[v] == 1)
	{
		medis.setC(nr[v], 101010);
		medis.setD(nr[v], D[v]);
	} else
	{
		medis.setC(nr[v], C[v]);
		medis.setD(nr[v], D[v]);
	}
	X = medis.get(nr[w], nr[tail[w]]);
	C[pa[w]] += min({X.cd, X.cc, X.dc + 1, X.dd + 1});
	D[pa[w]] += min({X.cd + 1, X.cc + 1, X.dc, X.dd});
	if (v != w)
		return fix(w);
	else if (v != 1)
		return fix(pa[v]);
}
int cat(int v)
{
	V[v] = -1;
	fix(v);
	return min(C[0], D[0]);
}
int dog(int v)
{
	V[v] = 1;
	fix(v);
	return min(C[0], D[0]);
}
int neighbor(int v)
{
	V[v] = 0;
	fix(v);
	return min(C[0], D[0]);
}/*
int main()
{
	initialize(3, {1, 1}, {2, 3});
	cout << cat(1) << endl;
	cout << C[0] << " " << D[0] << endl;
	cout << dog(2) << endl;
	cout << dog(3) << endl;
}*/

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