oj.uz

Submission #27122

# Submission time Handle Problem Language Result Execution time Memory
27122 2017-07-09T10:34:48 Z RayaBurong25_1 Amusement Park (JOI17_amusement_park) C++14
0 / 100
 273 ms 262144 KB 
#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);
	Vis[u] = 2;
	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] == 0)
			{
				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(".");
			if (Vis[v] != 2)
				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]]);
	}
	// printf("Joi fin\n");
}

#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] == 0)
			{
				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] = 2;
			if (Vis[v] != 2)
				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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6100 KB Output is correct
2 Incorrect 0 ms 6496 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 273 ms 262144 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5968 KB Output is correct
2 Correct 0 ms 5968 KB Output is correct
3 Incorrect 0 ms 5968 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 266 ms 262144 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 253 ms 262144 KB Memory limit exceeded
2 Halted 0 ms 0 KB -