oj.uz

Submission #27116

# Submission time Handle Problem Language Result Execution time Memory
27116 2017-07-09T10:27:29 Z RayaBurong25_1 Amusement Park (JOI17_amusement_park) C++14
10 / 100
 126 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);
	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]]);
	}
}

#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6100 KB Output is correct
2 Correct 0 ms 6892 KB Output is correct
3 Correct 6 ms 8212 KB Output is correct
4 Correct 0 ms 6364 KB Output is correct
5 Correct 0 ms 6364 KB Output is correct
6 Correct 0 ms 6628 KB Output is correct
7 Correct 3 ms 8212 KB Output is correct
8 Correct 3 ms 8740 KB Output is correct
9 Correct 6 ms 7948 KB Output is correct
10 Memory limit exceeded 103 ms 262144 KB Memory limit exceeded
11 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6100 KB Output is correct
2 Correct 0 ms 6100 KB Output is correct
3 Correct 0 ms 6100 KB Output is correct
4 Correct 16 ms 15084 KB Output is correct
5 Correct 9 ms 15076 KB Output is correct
6 Correct 15 ms 15080 KB Output is correct
7 Correct 18 ms 15076 KB Output is correct
8 Correct 12 ms 15080 KB Output is correct
9 Correct 102 ms 64944 KB Output is correct
10 Correct 126 ms 64952 KB Output is correct
11 Correct 89 ms 64948 KB Output is correct
12 Correct 0 ms 6100 KB Output is correct
13 Correct 0 ms 6100 KB Output is correct
14 Correct 0 ms 5836 KB Output is correct
15 Correct 0 ms 5836 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 79 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 53 ms 262144 KB Memory limit exceeded
2 Halted 0 ms 0 KB -