oj.uz

Submission #27099

# Submission time Handle Problem Language Result Execution time Memory
27099 2017-07-09T08:56:05 Z RayaBurong25_1 Amusement Park (JOI17_amusement_park) C++14
0 / 100
 9 ms 5912 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)
{
	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)
{
	int i, v, s = AdjList[u].size();
	for (i = 0; i < s; i++)
	{
		v = AdjList[u][i];
		if (v != pa && !Vis[v])
		{
			Pa[v] = u;
			Leaf[v] = Leaf[u];
			Leaf[v].erase(Leaf[v].find(u));
			Leaf[v].insert(v);
			Set[v] = Set[u];
			Role[v] = Role[*Leaf[v].begin()];
			Set[v].erase(Set[v].find(*Leaf[v].begin()));
			Set[v].insert(v);
			Vis[v] = 1;

			Explore(v, u);
		}
	}
}
void Joi(int N, int M, int A[], int B[], long long X, int T)
{
	int i, 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);

	s = AdjList[0].size();
	for (i = 0; i < s; i++)
	{
		v = AdjList[0][i];
		if (!Vis[v])
			break;
	}
	if (i == 1)
		Leaf[0].insert(0);

	std::set<int>::iterator it;
	for (it = Set[0].begin(); it != Set[0].end(); it++)
	{
		Set[*it] = Set[0];
		Leaf[*it] = Leaf[0];
	}
	for (it = Leaf[0].begin(); it != Leaf[0].end(); it++)
	{
		Explore(*it, Pa[*it]);
	}

	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)
{
	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)
{
	int i, v, s = AdjList[u].size();
	for (i = 0; i < s; i++)
	{
		v = AdjList[u][i];
		if (v != pa && !Vis[v])
		{
			Pa[v] = u;
			Leaf[v] = Leaf[u];
			Leaf[v].erase(Leaf[v].find(u));
			Leaf[v].insert(v);
			Set[v] = Set[u];
			Role[v] = Role[*Leaf[v].begin()];
			Set[v].erase(Set[v].find(*Leaf[v].begin()));
			Set[v].insert(v);
			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, 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);

	s = AdjList[0].size();
	for (i = 0; i < s; i++)
	{
		v = AdjList[0][i];
		if (!Vis[v])
			break;
	}
	if (i == 1)
		Leaf[0].insert(0);

	std::set<int>::iterator it;
	for (it = Set[0].begin(); it != Set[0].end(); it++)
	{
		Set[*it] = Set[0];
		Leaf[*it] = Leaf[0];
	}
	for (it = Leaf[0].begin(); it != Leaf[0].end(); it++)
	{
		Explore(*it, Pa[*it]);
	}

	PP = P;
	val[Role[P]] = V;
	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 5912 KB Output is correct
2 Runtime error 0 ms 3088 KB Execution killed because of forbidden syscall writev (20)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 3484 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 2956 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 3484 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 3484 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -