Submission #112854

#	Time	Username	Problem	Language	Result	Execution time	Memory
112854		Mahdi_Jfri	Amusement Park (JOI17_amusement_park)	C++14	83 / 100	32 ms	5420 KiB

Joi

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

using namespace std;

#define ll long long
#define pb push_back
#define bit(a , b) (((a)>>(b))&1)

const int maxn = 1e4 + 20;

vector<int> g1[maxn] , adj1[maxn] , shit1;

bool visited1[maxn];

int n1 , m1 , h1[maxn];

void plant1(int v)
{
	visited1[v] = 1;
	shit1.pb(v);
	for(auto u : g1[v])
		if(!visited1[u])
		{
			adj1[v].pb(u);
			h1[u] = h1[v] + 1;
			plant1(u);
		}
}

void Joi(int N, int M, int A[], int B[], long long X, int T)
{
	n1 = N , m1 = M;
	for(int i = 0; i < m1; i++)
		g1[A[i]].pb(B[i]) , g1[B[i]].pb(A[i]);
	plant1(0);

	int val = *max_element(h1 , h1 + n1) + 1;
	if(val < 60)
	{
		for(int i = 0; i < n1; i++)
		{
			if(i < 60)
				MessageBoard(shit1[i] , bit(X , i));
			else
				MessageBoard(shit1[i] , bit(X , h1[shit1[i]]));
		}
	}
	else
		for(int i = 0; i < n1; i++)
			MessageBoard(i , (X >> (h1[i] % 60))&1);
}

Ioi

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

using namespace std;

#define ll long long
#define pb push_back
#define bit(a , b) (((a)>>(b))&1)

const int maxn = 1e4 + 20;

vector<int> g[maxn] , adj[maxn] , shit;

bool visited[maxn];

bitset<maxn> have , tmphave;

int n , m , h[maxn] , par[maxn] , Pos[maxn];

void plant(int v)
{
	visited[v] = 1;

	Pos[v] = shit.size();
	shit.pb(v);
	for(auto u : g[v])
		if(!visited[u])
		{
			adj[v].pb(u);
			h[u] = h[v] + 1;
			par[u] = v;
			plant(u);
		}
}

vector<int> go(int v)
{
	vector<int> res;
	while(v)
		res.pb(v) , v = par[v];
	res.pb(v);

	reverse(res.begin() , res.end());
	return res;
}

void getval(int st , ll &V , int v)
{
	if(st == v)
		return;
	auto b = go(v);

	int ind = -1;
	for(int i = 0; i < h[v] + 1; i++)
		if(b[i] == st)
			ind = i;

	if(ind == -1)
	{
		assert(st != par[st]);
		st = par[st];
		V = Move(st);
		getval(st , V , v);
	}
	else
	{
		assert(st != b[ind + 1]);
		st = b[ind + 1];
		V = Move(st);
		getval(st , V , v);
	}
}

int getdist(int st , int v)
{
	if(st == v)
		return 0;
	auto b = go(v);

	int ind = -1;
	for(int i = 0; i < h[v] + 1; i++)
		if(b[i] == st)
			ind = i;

	if(ind == -1)
	{
		assert(st != par[st]);
		st = par[st];
		return getdist(st , v) + 1;
	}
	else
	{
		assert(st != b[ind + 1]);
		st = b[ind + 1];
		return getdist(st , v) + 1;
	}
}

ll Ioi(int N, int M, int A[], int B[], int st , int VV, int T)
{
	ll V = VV;
	n = N , m = M;
	for(int i = 0; i < m; i++)
		g[A[i]].pb(B[i]) , g[B[i]].pb(A[i]);
	plant(0);

	int val = *max_element(h , h + n) + 1;

	ll res = 0;
	if(val < 60)
	{
		while(Pos[st] >= 60)
		{
			res |= (V << h[st]) , have[h[st]] = 1;
			V = Move(par[st]);
			st = par[st];
		}

		int tmpst = st;
		tmphave = have;

		int L = 0;
		for(int i = Pos[st]; i < 60; i++)
		{
			if(have[i])
				continue;

			L += getdist(st , shit[i]);
			st = shit[i];
			have[i] = 1;
		}
		for(int i = 59; i >= 0; i--)
		{
			if(have[i])
				continue;

			L += getdist(st , shit[i]);
			st = shit[i];
			have[i] = 1;
		}

		have = tmphave;
		st = tmpst;
		int R = 0;
		for(int i = Pos[st]; i >= 0; i--)
		{
			if(have[i])
				continue;

			R += getdist(st , shit[i]);
			st = shit[i];
			have[i] = 1;
		}
		for(int i = 0; i < 60; i++)
		{
			if(have[i])
				continue;

			R += getdist(st , shit[i]);
			st = shit[i];
			have[i] = 1;
		}

		st = tmpst;
		have = tmphave;

		if(L < R)
		{
			for(int i = Pos[st]; i < 60; i++)
			{
				if(have[i])
					continue;

				getval(st , V , shit[i]);
				st = shit[i];
				res |= (V << i);
				have[i] = 1;
			}
			for(int i = 59; i >= 0; i--)
			{
				if(have[i])
					continue;

				getval(st , V , shit[i]);
				st = shit[i];
				res |= (V << i);
				have[i] = 1;
			}
		}
		else
		{
			for(int i = Pos[st]; i >= 0; i--)
			{
				if(have[i])
					continue;

				getval(st , V , shit[i]);
				st = shit[i];
				res |= (V << i);
				have[i] = 1;
			}
			for(int i = 0; i < 60; i++)
			{
				if(have[i])
					continue;

				getval(st , V , shit[i]);
				st = shit[i];
				res |= (V << i);
				have[i] = 1;
			}
		}
	}
	else
	{
		if(h[st] + 1 < 60)
		{
			while(st)
				V = Move(par[st]) , st = par[st];

			auto tmp = go(max_element(h , h + n) - h);

			for(int i = 0; i < 60; i++)
			{
				if(st != tmp[i])
					V = Move(tmp[i]);
				st = tmp[i];
				res |= (V << i);
			}
		}
		else
		{
			for(int i = 0; i < 60; i++)
			{
				res |= (V << (h[st] % 60));
				if(st != par[st])
					V = Move(par[st]);
				st = par[st];
			}
		}
	}

	return res;
}

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