Submission #1235744

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235744		gs13105	The Ties That Guide Us (CEOI23_incursion)	C++20	100 / 100	152 ms	7456 KiB

incursion

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

#include "incursion.h"

int n;
vector<int> adj[45010];
vector<int> cen;
int siz[45010];
int par[45010];

void f(int x, int p)
{
	bool ok = 1;
	siz[x] = 1;
	for(int y : adj[x])
	{
		if(y == p)
			continue;
		f(y, x);
		siz[x] += siz[y];
		if(siz[y] > n / 2)
			ok = 0;
	}
	if(n - siz[x] > n / 2)
		ok = 0;
	if(ok)
		cen.push_back(x);
}

void g(int x, int p)
{
	par[x] = p;
	siz[x] = 1;
	for(int y : adj[x])
	{
		if(y == p)
			continue;
		g(y, x);
		siz[x] += siz[y];
	}
}

void init(vector<pair<int, int>> &F)
{
	n = (int)F.size() + 1;
	for(auto [x, y] : F)
	{
		adj[x].push_back(y);
		adj[y].push_back(x);
	}

	f(1, -1);
	if((int)cen.size() == 1)
		cen.push_back(-1);
	assert((int)cen.size() == 2);

	g(cen[0], cen[1]);
	if(cen[1] != -1)
		g(cen[1], cen[0]);
}

vector<int> mark(vector<pair<int, int>> F, int safe)
{
	init(F);
	vector<int> res(n);
	int x = safe;
	while(1)
	{
		res[x - 1] = 1;
		if(x == cen[0] || x == cen[1])
			break;
		x = par[x];
	}
	return res;
}

void locate(vector<pair<int, int>> F, int curr, int t)
{
	init(F);
	int x = curr;
	while(t == 0)
	{
		t = visit(par[x]);
		x = par[x];
	}
	while(1)
	{
		vector<pair<int, int>> nx;
		for(int y : adj[x])
		{
			if(y == par[x])
				continue;
			nx.push_back({ siz[y], y });
		}
		sort(nx.rbegin(), nx.rend());
		bool ok = 1;
		for(auto [_, y] : nx)
		{
			if(visit(y))
			{
				ok = 0;
				x = y;
				break;
			}
			visit(x);
		}
		if(ok)
			return;
	}
}

• Subtask 0: 0 / 0
• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40