Submission #112861

#	Time	Username	Problem	Language	Result	Execution time	Memory
112861		ckodser	Amusement Park (JOI17_amusement_park)	C++14	79 / 100	36 ms	3908 KiB

Joi

#include<bits/stdc++.h>
#include "Joi.h"
#define pb push_back
using namespace std;
const int MXN = 12345;
vector < int > Adj[MXN];
void Joi(int N, int M, int A[], int B[], long long X, int T)
{
	for (int i = 0; i < M; i++)
		Adj[A[i]].pb(B[i]), Adj[B[i]].pb(A[i]);
	vector < int > D(N, -1);
	vector < int > P(N, -1);
	vector < int > qu(N, 0);
	int l = 0, r = 0;
	qu[r ++] = 0; D[0] = 0;
	bool OK = 0;
	while (r - l)
	{
		int v = qu[l ++];
		if (D[v] == 59)
			OK = 1;
		for (int &u : Adj[v])
			if (D[u] == -1)
				D[u] = (D[v] + 1) % 60, P[u] = v, qu[r ++] = u;
	}
	if (OK)
	{
		for (int i = 0; i < N; i++)
			MessageBoard(i, (X >> D[i]) & 1LL);
		return ;
	}
	vector < int > F(N, -1);
	vector < int > rev(N, -1);
	for (int i = 0; i < N; i++)
		rev[qu[i]] = i;
	for (int i = 0; i < 60; i++)
		MessageBoard(qu[i], (X >> i) & 1LL), F[qu[i]] = i;
	for (int i = 60; i < N; i++)
	{
		int v = qu[i];
		vector < int > Mark(60, 0);
		for (int p = P[v]; p >= 0; p = P[p])
			Mark[F[p]] = 1;
		F[v] = 59;
		while (Mark[F[v]])
			F[v] --;
		MessageBoard(v, (X >> F[v]) & 1LL);
	}
	return ;
}

Ioi

#include<bits/stdc++.h>
#include "Ioi.h"
#define pb push_back
using namespace std;
const int MXN = 12345;
bool toSee[MXN], seen[MXN];
vector < int > vec, Adj[MXN];
void DFS(int v)
{
	seen[v] = 1;
	for (int &u : Adj[v])
		if (!seen[u] && toSee[u])
		{
			vec.pb(u);
			DFS(u);
			vec.pb(v);
		}
}
long long Ioi(int N, int M, int A[], int B[], int ST, int VL, int T)
{
	for (int i = 0; i < M; i++)
		Adj[A[i]].pb(B[i]), Adj[B[i]].pb(A[i]);
	vector < int > D(N, -1);
	vector < int > qu(N, 0);
	vector < int > P(N, -1);
	int l = 0, r = 0;
	qu[r ++] = 0; D[0] = 0;
	bool OK = 0;
	while (r - l)
	{
		int v = qu[l ++];
		if (D[v] % 60 == 59)
			OK = 1;
		for (int &u : Adj[v])
			if (D[u] == -1)
				D[u] = D[v] + 1, P[u] = v, qu[r ++] = u;
	}
	if (OK)
	{
		if (D[ST] >= 59)
		{
			long long X = 0;
			for (int i = 0; i < 60; i++)
			{
				X |= (1LL * VL) << (D[ST] % 60);
				if (i < 59)
					ST = P[ST], VL = Move(ST);
			}
			return (X);
		}
		int start = -1;
		for (int i = 0; i < N; i++)
			if (D[i] == 59)
				start = i;
		assert(start != -1);
		vector < int > ids(60, -1);
		for (int i = 59; i >= 0; i--)
			ids[i] = start, start = P[start];
		long long X = 0;
		while (ST != 0)
			ST = P[ST], VL = Move(ST);
		for (int i = 0; i < 60; i++)
		{
			X |= (1LL * VL) << (D[ST] % 60);
			if (i + 1 < 60)
				ST = ids[i + 1], VL = Move(ST);
		}
		return (X);
	}
	vector < int > F(N, -1);
	vector < int > rev(N, -1);
	for (int i = 0; i < N; i++)
		rev[qu[i]] = i;
	for (int i = 0; i < 60; i++)
		F[qu[i]] = i;
	for (int i = 60; i < N; i++)
	{
		int v = qu[i];
		vector < int > Mark(60, 0);
		for (int p = P[v]; p >= 0; p = P[p])
			Mark[F[p]] = 1;
		F[v] = 59;
		while (Mark[F[v]])
			F[v] --;
	}
	long long X = 0;
	for (int i = 0; i < 60; i++)
		toSee[qu[i]] = 1;
	while (ST != 0)
	{
		X |= (1LL * VL) << (F[ST]);
		//toSee[qu[F[ST]]] = 0;
		ST = P[ST]; VL = Move(ST);
	}
	X |= VL;
	DFS(0);
	for (int v : vec)
	{
		ST = v; VL = Move(ST);
		X |= (1LL * VL) << (F[ST]);
	}
	return (X);
}

• Subtask 1: 8 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 51 / 55
• Subtask 5: 0 / 17