Submission #27116

#	Time	Username	Problem	Language	Result	Execution time	Memory
27116		RayaBurong25_1	Amusement Park (JOI17_amusement_park)	C++14	10 / 100	126 ms	262144 KiB

Joi

#include <stdio.h>
#include "Joi.h"
#include <vector>
#include <set>
static std::vector<int> AdjList[10005];
static int Role[10005];
static int Vis[10005];
static int Pa[10005];
static std::set<int> Set[10005];
static std::set<int> Leaf[10005];
static int cnt;
static void InitSet(int u, int pa)
{
	// printf("InitSet %d %d\n", u, pa);
	int i, v, s = AdjList[u].size();
	Pa[u] = pa;
	Role[u] = cnt;
	cnt++;
	Set[0].insert(u);
	Vis[u] = 1;
	if (cnt == 60)
	{
		// Leaf[0].insert(u);
		return;
	}
	for (i = 0; i < s; i++)
	{
		v = AdjList[u][i];
		if (v != pa && !Vis[v])
			InitSet(v, u);
		if (cnt == 60)
			return;
	}
}
static void Explore(int u, int pa)
{
	// printf("Explore %d %d\n", u, pa);
	// std::set<int>::iterator it;
	// for (it = Leaf[u].begin(); it != Leaf[u].end(); it++)
	// 	printf(" %d\n", *it);
	int i, er, j, v, s = AdjList[u].size(), sj;
	for (i = 0; i < s; i++)
	{
		v = AdjList[u][i];
		if (v != pa)
		{
			if (!Vis[v])
			{
				Pa[v] = u;
				// printf(".");
				Leaf[v] = Leaf[u];
				// printf(".");
				Leaf[v].erase(u);
				// printf(".");
				Set[v] = Set[u];
				// printf(".");
				er = *Leaf[v].begin();
				Role[v] = Role[*Leaf[v].begin()];
				// printf(".");
				sj = AdjList[er].size();
				for (j = 0; j < sj; j++)
					if (Set[v].find(AdjList[er][j]) != Set[v].end())
						break;
				Set[v].erase(er);
				// printf("set v%d erase er%d %d\n", v, er, Set[v].size());
				// printf(".");
				Leaf[v].insert(AdjList[er][j]);
				// printf(".");
				Leaf[v].erase(Leaf[v].begin());
				// printf(".");
				Set[v].insert(v);
				// printf(".");
				Leaf[v].insert(v);
			}
			// printf(".");
			Vis[v] = 1;

			Explore(v, u);
		}
	}
}
void Joi(int N, int M, int A[], int B[], long long X, int T)
{
	int i, j, v, s;
	for (i = 0; i < M; i++)
	{
		AdjList[A[i]].push_back(B[i]);
		AdjList[B[i]].push_back(A[i]);
	}
	InitSet(0, -1);

	std::set<int>::iterator it;
	int deg;
	for (it = Set[0].begin(); it != Set[0].end(); it++)
	{
		j = *it;
		s = AdjList[j].size();
		deg = 0;
		for (i = 0; i < s; i++)
		{
			v = AdjList[j][i];
			if (Vis[v])
				deg++;
		}
		if (deg == 1)
			Leaf[0].insert(j);
	}

	for (it = Set[0].begin(); it != Set[0].end(); it++)
	{
		Set[*it] = Set[0];
		Leaf[*it] = Leaf[0];
	}
	Explore(0, -1);

	int val[60];
	for (i = 0; i < 60; i++)
	{
		val[i] = X%2;
		// printf("%d\n", val[i]);
		X >>= 1;
	}
	for (i = 0; i < N; i++)
	{
		// printf("i %d = %d\n", i, Role[i]);
		MessageBoard(i, val[Role[i]]);
	}
}

Ioi

#include <stdio.h>
#include "Ioi.h"
#include <vector>
#include <set>
static std::vector<int> AdjList[10005];
static int Role[10005];
static int Vis[10005];
static int Pa[10005];
static std::set<int> Set[10005];
static std::set<int> Leaf[10005];
static int cnt;
static void InitSet(int u, int pa)
{
	// printf("InitSet %d %d\n", u, pa);
	int i, v, s = AdjList[u].size();
	Pa[u] = pa;
	Role[u] = cnt;
	cnt++;
	Set[0].insert(u);
	Vis[u] = 1;
	if (cnt == 60)
	{
		// Leaf[0].insert(u);
		return;
	}
	for (i = 0; i < s; i++)
	{
		v = AdjList[u][i];
		if (v != pa && !Vis[v])
			InitSet(v, u);
		if (cnt == 60)
			return;
	}
}
static void Explore(int u, int pa)
{
	// printf("Explore %d %d\n", u, pa);
	// std::set<int>::iterator it;
	// for (it = Leaf[u].begin(); it != Leaf[u].end(); it++)
	// 	printf(" %d\n", *it);
	int i, er, j, v, s = AdjList[u].size(), sj;
	for (i = 0; i < s; i++)
	{
		v = AdjList[u][i];
		if (v != pa)
		{
			if (!Vis[v])
			{
				Pa[v] = u;
				// printf(".");
				Leaf[v] = Leaf[u];
				// printf(".");
				Leaf[v].erase(u);
				// printf(".");
				Set[v] = Set[u];
				// printf(".");
				er = *Leaf[v].begin();
				Role[v] = Role[*Leaf[v].begin()];
				// printf(".");
				sj = AdjList[er].size();
				for (j = 0; j < sj; j++)
					if (Set[v].find(AdjList[er][j]) != Set[v].end())
						break;
				Set[v].erase(er);
				// printf("set v%d erase er%d %d\n", v, er, Set[v].size());
				// printf(".");
				Leaf[v].insert(AdjList[er][j]);
				// printf(".");
				Leaf[v].erase(Leaf[v].begin());
				// printf(".");
				Set[v].insert(v);
				// printf(".");
				Leaf[v].insert(v);
			}
			// printf(".");
			Vis[v] = 1;

			Explore(v, u);
		}
	}
}
static int val[60];
static int PP;
void GetVal(int u, int pa)
{
	// printf("GetVal u%d\n", u);
	int i, v, s = AdjList[u].size();
	for (i = 0; i < s; i++)
	{
		v = AdjList[u][i];
		if (v != pa && !Vis[v] && Set[PP].find(v) != Set[PP].end())
		{
			val[Role[v]] = Move(v);
			Vis[v] = 1;
			GetVal(v, u);
			Move(u);
		}
	}
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T)
{
	int i, j, v, s;
	for (i = 0; i < M; i++)
	{
		AdjList[A[i]].push_back(B[i]);
		AdjList[B[i]].push_back(A[i]);
	}
	InitSet(0, -1);

	std::set<int>::iterator it;
	int deg;
	for (it = Set[0].begin(); it != Set[0].end(); it++)
	{
		j = *it;
		s = AdjList[j].size();
		deg = 0;
		for (i = 0; i < s; i++)
		{
			v = AdjList[j][i];
			if (Vis[v])
				deg++;
		}
		if (deg == 1)
			Leaf[0].insert(j);
	}

	for (it = Set[0].begin(); it != Set[0].end(); it++)
	{
		Set[*it] = Set[0];
		Leaf[*it] = Leaf[0];
	}
	Explore(0, -1);

	PP = P;
	val[Role[P]] = V;
	// for (i = 0; i < N; i++)
	// {
	// 	printf("i%d %d ", i, Vis[i]);
	// 	for (it = Set[i].begin(); it != Set[i].end(); it++)
	// 		printf("%d ", *it);
	// 	printf("\n");
	// }
	for (i = 0; i < N; i++)
		Vis[i] = 0;
	Vis[P] = 1;
	GetVal(P, -1);

	long long X = 0;
	for (i = 59; i >= 0; i--)
	{
		// printf("val %d = %d\n", i, val[i]);
		X <<= 1;
		X += val[i];
		// printf("  X %lld\n", X);
	}
	// printf("X %lld", X);
	return X;
}

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