oj.uz

Submission #112842

# Submission time Handle Problem Language Result Execution time Memory
112842 2019-05-22T06:50:03 Z ckodser Amusement Park (JOI17_amusement_park) C++14
10 / 100
 27 ms 3896 KB 
#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 ;
}
#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);
				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) << (D[ST] % 60);
		toSee[qu[D[ST] % 60]] = 0;
		ST = P[ST]; VL = Move(ST);
	}
	X |= VL;
	DFS(0);
	for (int v : vec)
	{
		ST = v; VL = Move(ST);
		X |= (1LL * VL) << (D[ST] % 60);
	}
	return (X);
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 1416 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 3896 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1408 KB Output is correct
2 Correct 4 ms 1280 KB Output is correct
3 Correct 6 ms 1288 KB Output is correct
4 Correct 6 ms 1692 KB Output is correct
5 Correct 6 ms 1692 KB Output is correct
6 Correct 6 ms 1692 KB Output is correct
7 Correct 7 ms 1692 KB Output is correct
8 Correct 6 ms 1572 KB Output is correct
9 Correct 13 ms 3008 KB Output is correct
10 Correct 14 ms 3016 KB Output is correct
11 Correct 14 ms 2888 KB Output is correct
12 Correct 4 ms 1416 KB Output is correct
13 Correct 5 ms 1456 KB Output is correct
14 Correct 2 ms 1280 KB Output is correct
15 Correct 4 ms 1280 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 3860 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 3856 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -