oj.uz

답안 #27106

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
27106 2017-07-09T09:20:11 Z RayaBurong25_1 Amusement Park (JOI17_amusement_park) C++14
10 / 100
 269 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)
{
	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\n", u);
	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 && !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].insert(AdjList[er][j]);
			// printf(".");
			Set[v].erase(*Leaf[v].begin());
			// 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, 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)
{
	// printf("Explore %d\n", u);
	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 && !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].insert(AdjList[er][j]);
			// printf(".");
			Set[v].erase(*Leaf[v].begin());
			// 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, 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 5912 KB Output is correct
2 Incorrect 0 ms 6176 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Memory limit exceeded 249 ms 262144 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 6176 KB Output is correct
2 Correct 0 ms 6176 KB Output is correct
3 Correct 0 ms 6176 KB Output is correct
4 Correct 18 ms 15200 KB Output is correct
5 Correct 9 ms 15192 KB Output is correct
6 Correct 6 ms 15196 KB Output is correct
7 Correct 15 ms 15196 KB Output is correct
8 Correct 15 ms 15196 KB Output is correct
9 Correct 128 ms 65324 KB Output is correct
10 Correct 112 ms 65316 KB Output is correct
11 Correct 106 ms 65320 KB Output is correct
12 Correct 0 ms 6176 KB Output is correct
13 Correct 0 ms 6176 KB Output is correct
14 Correct 0 ms 5912 KB Output is correct
15 Correct 0 ms 5912 KB Output is correct

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Memory limit exceeded 253 ms 262144 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Memory limit exceeded 269 ms 262144 KB Memory limit exceeded
2 Halted 0 ms 0 KB -