oj.uz

Submission #27129

# Submission time Handle Problem Language Result Execution time Memory
27129 2017-07-09T13:24:32 Z RayaBurong25_1 Amusement Park (JOI17_amusement_park) C++14
10 / 100
 135 ms 62780 KB 
#include <stdio.h>
#include "Joi.h"
#include <vector>
#include <set>
#define SZ 60
static std::vector<int> AdjList[10005];
static std::set<int> Set[10005];
static int Vis[10005];
static int Role[10005];
static void FirstSet(int u, int pa)
{
	if (Set[0].size() < SZ)
	{
		Role[u] = Set[0].size();
		Set[0].insert(u);
	}
	int i, j, v, s = AdjList[u].size();
	Vis[u] = 1;
	for (i = 0; i < s; i++)
	{
		v = AdjList[u][i];
		if (v != pa)
		{
			if (!Vis[v])
				FirstSet(v, u);
			else
			{
				AdjList[u].erase(AdjList[u].begin() + i);
				for (j = 0; j < AdjList[v].size(); j++)
					if (AdjList[v][j] == u)
						break;
				AdjList[v].erase(AdjList[v].begin() + j);
				i--;
			}
		}
	}
}
// static int HELLO;
static void OtherSet(int u, int pa)
{
	// printf("OtherSet u%d pa%d\n", u, pa);
	// HELLO++;
	int i, j, v, s, d;
	if (u != 0)
	{
		Set[u] = Set[pa];
		if (Set[u].find(u) == Set[u].end())
		{
			std::set<int>::iterator it;
			Set[u].insert(u);
			// for (it = Set[u].begin(); it != Set[u].end(); it++)
			// 	printf("%d ", *it);
			// printf("\n");
			for (it = Set[u].begin(); it != Set[u].end(); it++)
			{
				if (*it == pa || *it == u)
					continue;
				s = AdjList[*it].size();
				d = 0;
				for (j = 0; j < s; j++)
				{
					if (Set[u].find(AdjList[*it][j]) != Set[u].end())
					{
						// printf("%d-%d\n", *it, AdjList[*it][j]);
						d++;
					}
					// else
					// 	printf("%d-%dX\n", *it, AdjList[*it][j]);
				}
				if (d == 1)
					break;
			}
			if (it != Set[u].end())
			{
				Role[u] = Role[*it];
				Set[u].erase(it);
				// printf("u %d pa %d erase %d d %d\n", u, pa, *it, d);
			}
		}
	}
	s = AdjList[u].size();
	for (i = 0; i < s; i++)
	{
		v = AdjList[u][i];
		if (v != pa && Set[v].size() == 0)
		{
			OtherSet(v, u);
		}
	}
}
void Joi(int N, int M, int A[], int B[], long long X, int T)
{
	int i;
	for (i = 0; i < M; i++)
	{
		AdjList[A[i]].push_back(B[i]);
		AdjList[B[i]].push_back(A[i]);
	}
	FirstSet(0, -1);
	// printf("FirstSet fin\n");
	// for (i = 0; i < N; i++)
	// 	HELLO += AdjList[i].size();
	// printf("HELLO %d\n", HELLO);
	OtherSet(0, -1);
	// printf("OtherSet fin %d\n", HELLO);

	int val[SZ];
	for (i = 0; i < SZ; i++)
	{
		val[i] = X%2;
		X >>= 1;
	}
	for (i = 0; i < N; i++)
	{
		MessageBoard(i, val[Role[i]]);
	}
	// printf("Joi fin\n");
}
#include <stdio.h>
#include "Ioi.h"
#include <vector>
#include <set>
#define SZ 60
static std::vector<int> AdjList[10005];
static std::set<int> Set[10005];
static int Vis[10005];
static int Role[10005];
static void FirstSet(int u, int pa)
{
	if (Set[0].size() < SZ)
	{
		Role[u] = Set[0].size();
		Set[0].insert(u);
	}
	int i, j, v, s = AdjList[u].size();
	Vis[u] = 1;
	for (i = 0; i < s; i++)
	{
		v = AdjList[u][i];
		if (v != pa)
		{
			if (!Vis[v])
				FirstSet(v, u);
			else
			{
				AdjList[u].erase(AdjList[u].begin() + i);
				for (j = 0; j < AdjList[v].size(); j++)
					if (AdjList[v][j] == u)
						break;
				AdjList[v].erase(AdjList[v].begin() + j);
				i--;
			}
		}
	}
}
// static int HELLO;
static void OtherSet(int u, int pa)
{
	// printf("OtherSet u%d\n", u);
	// HELLO++;
	int i, j, v, s, d;
	if (u != 0)
	{
		Set[u] = Set[pa];
		if (Set[u].find(u) == Set[u].end())
		{
			std::set<int>::iterator it;
			Set[u].insert(u);
			for (it = Set[u].begin(); it != Set[u].end(); it++)
			{
				if (*it == pa || *it == u)
					continue;
				s = AdjList[*it].size();
				d = 0;
				for (j = 0; j < s; j++)
				{
					if (Set[u].find(AdjList[*it][j]) != Set[u].end())
						d++;
				}
				if (d == 1)
					break;
			}
			if (it != Set[u].end())
			{
				Role[u] = Role[*it];
				Set[u].erase(it);
			}
		}
	}
	s = AdjList[u].size();
	for (i = 0; i < s; i++)
	{
		v = AdjList[u][i];
		if (v != pa && Set[v].size() == 0)
		{
			OtherSet(v, u);
		}
	}
}
static int val[SZ];
// static int HELLO;
void GetVal(int P, int u, int pa)
{
	// printf("GetVal %d %d\n", u, pa);
	// HELLO++;
	int i, v, s = AdjList[u].size();
	Vis[u] = 1;
	for (i = 0; i < s; i++)
	{
		v = AdjList[u][i];
		if (v != pa && !Vis[v] && Set[P].find(v) != Set[P].end())
		{
			val[Role[v]] = Move(v);
			GetVal(P, v, u);
			Move(u);
		}
	}
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T)
{
	int i;
	for (i = 0; i < M; i++)
	{
		AdjList[A[i]].push_back(B[i]);
		AdjList[B[i]].push_back(A[i]);
	}
	FirstSet(0, -1);
	OtherSet(0, -1);

	val[Role[P]] = V;
	for (i = 0; i < N; i++)
		Vis[i] = 0;
	std::set<int>::iterator it;
	// for (i = 0; i < N; i++)
	// 	printf("%d\n", Set[i].size());
	GetVal(P, P, -1);
	// printf("GetVal fin %d %d\n", Set[P].size(), HELLO);

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

Compilation message

Joi.cpp: In function 'void FirstSet(int, int)':
Joi.cpp:29:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (j = 0; j < AdjList[v].size(); j++)
                   ^

Ioi.cpp: In function 'void FirstSet(int, int)':
Ioi.cpp:29:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (j = 0; j < AdjList[v].size(); j++)
                   ^

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5156 KB Output is correct
2 Correct 0 ms 5420 KB Output is correct
3 Correct 3 ms 6476 KB Output is correct
4 Correct 0 ms 5156 KB Output is correct
5 Correct 0 ms 5156 KB Output is correct
6 Correct 0 ms 5684 KB Output is correct
7 Correct 6 ms 6476 KB Output is correct
8 Correct 3 ms 6212 KB Output is correct
9 Correct 3 ms 6212 KB Output is correct
10 Runtime error 0 ms 2312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 2708 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5156 KB Output is correct
2 Correct 0 ms 5156 KB Output is correct
3 Correct 0 ms 5156 KB Output is correct
4 Correct 9 ms 13976 KB Output is correct
5 Correct 18 ms 13972 KB Output is correct
6 Correct 22 ms 13972 KB Output is correct
7 Correct 9 ms 13976 KB Output is correct
8 Correct 15 ms 13968 KB Output is correct
9 Correct 89 ms 62780 KB Output is correct
10 Correct 114 ms 62772 KB Output is correct
11 Correct 135 ms 62764 KB Output is correct
12 Correct 0 ms 5156 KB Output is correct
13 Correct 0 ms 5156 KB Output is correct
14 Correct 0 ms 4892 KB Output is correct
15 Correct 0 ms 4892 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 2708 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 2708 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -