Submission #1183871

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183871		catch_me_if_you_can	Amusement Park (JOI17_amusement_park)	C++20	82 / 100	13 ms	2120 KiB

Joi

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

using namespace std;
#define ll long long
#define in array<int, 2>
#define pb push_back
#define pob pop_back

#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

const int MX = 1e4 + 20;
const int S = 60;

vector<int> RL_J(MX, -1);

int leader_J(int u)
{
	if(RL_J[u] < 0)
		return u;
	else
		return RL_J[u] = leader_J(RL_J[u]);
}

bool merge_J(int u, int v)
{
	u = leader_J(u);
	v = leader_J(v);
	if(u == v)
		return false;
	if(RL_J[u] < RL_J[v])
		swap(u, v);
	RL_J[v]+=RL_J[u];
	RL_J[u] = v;
	return true;
}

vector<int> adj_J[MX];

vector<int> pa_J(MX);

vector<int> DEP_J(MX);

in furthest_J(int u, int p, int lvl)
{
	DEP_J[u] = lvl;
	in d = {lvl, u};
	pa_J[u] = p;
	for(int v: adj_J[u])
	{
		if(v==p)
			continue;
		d = max(d, furthest_J(v, u, lvl+1));
	}
	//cout << "For u = " << d[0] << " " << d[1] << endl;
	return d;
}

vector<int> flt_J;
vector<bool> hmm_J;

void pre(int u, int p, int vertex)
{
	if(u == vertex)
	{
		hmm_J[u] = 1;
		return;
	}
	for(int v: adj_J[u])
	{
		if(v==p)
			continue;
		pre(v, u, vertex);
		hmm_J[u] = hmm_J[u]|hmm_J[v];
	}
}

void order_J(int u, int p)
{
	if(flt_J.size() < S)
		flt_J.pb(u);
	int x = -1;
	for(int v: adj_J[u])
	{
		if(v == p)
			continue;
		if(hmm_J[v])
		{
			x = v;
			continue;
		}
		order_J(v, u);
	}
	if(x != -1)
		order_J(x, u);
	return;
}

void Joi(int N, int M, int A[], int B[], ll X, int T)
{
	for(int i = 0; i < N; i++)
		adj_J[i].clear();
	for(int i = 0; i < M; i++)
	{
		if(merge_J(A[i], B[i]))
		{
			adj_J[A[i]].pb(B[i]);
			adj_J[B[i]].pb(A[i]);	
		}
	}
	int f1 = furthest_J(0, -1, 0)[1];
	auto [D, f2] = furthest_J(f1, -1, 0);
	if(D >= (S-1))
	{
		for(int i = 0; i < N; i++)
			MessageBoard(i, (X>>(DEP_J[i]%S))&1);
		return;
	}
	vector<int> pth;
	int GG = f2;
	while(GG != -1)
	{
		pth.pb(GG);
		GG = pa_J[GG];
	}
	reverse(pth.begin(), pth.end());
	int root = pth[pth.size()/2];
	hmm_J.assign(N, false);
	pre(root, -1, f1);
	order_J(root, -1);
	vector<int> send(N, 0);
	for(int i = 0; i < S; i++)
		send[flt_J[i]] = (X>>i)&1;
	for(int i = 0; i < N; i++)
		MessageBoard(i, send[i]);
	return;
}

Ioi

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

using namespace std;

#define ll long long
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

const int MX = 1e4 + 20;
const int S = 60;

vector<int> RL_I(MX, -1);

int leader_I(int u)
{
	if(RL_I[u] < 0)
		return u;
	else
		return RL_I[u] = leader_I(RL_I[u]);
}

bool merge_I(int u, int v)
{
	u = leader_I(u);
	v = leader_I(v);
	if(u == v)
		return false;
	if(RL_I[u] < RL_I[v])
		swap(u, v);
	RL_I[v]+=RL_I[u];
	RL_I[u] = v;
	return true;
}

vector<int> adj_I[MX];

vector<int> pa_I(MX);

vector<int> DEP_I(MX);

in furthest_I(int u, int p, int lvl)
{
	DEP_I[u] = lvl;
	in d = {lvl, u};
	pa_I[u] = p;
	for(int v: adj_I[u])
	{
		if(v==p)
			continue;
		d = max(d, furthest_I(v, u, lvl+1));
	}
	//cout << "For u = " << d[0] << " " << d[1] << endl;
	return d;
}

vector<int> flt_I;
vector<bool> hmm_I;

void pre_I(int u, int p, int vertex)
{
	pa_I[u] = p;
	if(u == vertex)
	{
		hmm_I[u] = 1;
		return;
	}
	for(int v: adj_I[u])
	{
		if(v==p)
			continue;
		pre_I(v, u, vertex);
		hmm_I[u] = hmm_I[u]|hmm_I[v];
	}
}

void order_I(int u, int p, int s)
{
	//cout << "Currently at = " << u << endl;
	if(flt_I.size() < S)
		flt_I.pb(s);
	else
		return;
	int x = -1;
	for(int v: adj_I[u])
	{
		if(v == p)
			continue;
		if(hmm_I[v])
		{
			x = v;
			continue;
		}
		//cout << "Mroving to " << v << endl;
		int TT = Move(v);
		//cout << "no problem " << endl;
		order_I(v, u, TT);
		if(flt_I.size() == S)
			return;
		//cout << "Mroving to " << u << endl;
		Move(u);
		//cout << "no problem" << endl;
	}
	if(x != -1)
		order_I(x, u, Move(x));
	return;
}

long long Ioi(int N, int M, int A[], int B[], int p, int v, int T)
{
	for(int i = 0; i < N; i++)
		adj_I[i].clear();
	for(int i = 0; i < M; i++)
	{
		if(merge_I(A[i], B[i]))
		{
			adj_I[A[i]].pb(B[i]);
			adj_I[B[i]].pb(A[i]);	
		}
	}
	int f1 = furthest_I(0, -1, 0)[1];
	auto [D, f2] = furthest_I(f1, -1, 0);
	//cout << f1 << " " << D << " " << f2 << endl;
	vector<int> pth;
	int GG = f2;
	while(GG != -1)
	{
		pth.pb(GG);
		GG = pa_I[GG];
	}
	reverse(pth.begin(), pth.end());
	/*for(int x: pth)
		cout << x << " ";
	cout << endl;*/
	if(D >= (S-1))
	{
		int ans[S];
		if(DEP_I[p] >= (S-1))
		{
			ans[(DEP_I[p]%S)] = v;
			for(int i = 1; i < S; i++)
			{
				p = pa_I[p];
				ans[(DEP_I[p]%S)] = Move(p);
			}
		}
		else
		{
			int x = p;
			if(x != f1)
			{
				//cout << "hi" << endl;
				while(pa_I[x] != f1)
				{
					//cout << "Moved to pa_i[x] = " << pa_I[x] << endl;
					Move(pa_I[x]);
					x = pa_I[x];
				}
				ans[0] = Move(f1);
			}
			else
				ans[0] = v;
			for(int i = 1; i < S; i++)
				ans[i] = Move(pth[i]);
		}
		ll ANS = 0;
		for(int i = 0; i < S; i++)
		{
			if(ans[i])
				ANS^=(1ll<<i);
		}
		return ANS;
	}
	int root = pth[pth.size()/2];
	hmm_I.assign(N, false);
	flt_I.clear();
	
	pre_I(root, -1, f1);
	//cout << f1 << endl;
	//cout << root << endl;
	while(p != root)
	{
		p = pa_I[p];
		//cout << "Moving to " << p << endl;
		v = Move(p);
		//cout << "No issue " << endl;
	}
	order_I(root, -1, v);
	ll ANS = 0;
	for(int i = 0; i < S; i++)
		if(flt_I[i])
			ANS^=(1ll<<i);
	return ANS;
}

• Subtask 1: 8 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 54 / 55
• Subtask 5: 0 / 17