oj.uz

Submission #130675

# Submission time Handle Problem Language Result Execution time Memory
130675 2019-07-15T19:50:19 Z tutis Amusement Park (JOI17_amusement_park) C++17
72 / 100
 76 ms 7764 KB 
#include "Joi.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
mt19937_64 rng(1561561);
int bitas[11000];
vector<int>adj[11000];
set<int>aplankyta;
int t = 0;
set<pair<int, int>>EE;
void dfs(int v, int p = -2)
{
	if (aplankyta.count(v))
		return;
	EE.insert({v, p});
	EE.insert({p, v});
	aplankyta.insert(v);
	t++;
	t %= 60;
	bitas[v] = t;
	for (int x : adj[v])
	{
		dfs(x, v);
	}
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
	vector<int>PP(N);
	iota(PP.begin(), PP.end(), 0);
	shuffle(PP.begin(), PP.end(), rng);
	for (int i = 0; i < M; i++)
	{
		adj[A[i]].push_back(B[i]);
		adj[B[i]].push_back(A[i]);
	}
	for (int i = 0; i < N; i++)
		shuffle(adj[i].begin(), adj[i].end(), rng);
	dfs(rng() % N);
	for (int i = 0; i < N; i++)
	{
		int s = 0;
		if ((X & (1ll << bitas[i])) > 0)
			s = 1;
		MessageBoard(i, s);
	}
}
#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937_64 rng(1561561);
int bitas[11000];
vector<int>adj[11000];
set<int>aplankyta;
int t = 0;
set<pair<int, int>>EE;
vector<int>order;
void dfs(int v, int p = -2)
{
	if (aplankyta.count(v))
		return;
	order.push_back(v);
	EE.insert({v, p});
	EE.insert({p, v});
	aplankyta.insert(v);
	t++;
	t %= 60;
	bitas[v] = t;
	bool ok = false;
	for (int x : adj[v])
	{
		if (aplankyta.count(x))
			continue;
		dfs(x, v);
		order.push_back(v);
		ok = true;
	}
	if (ok == false)
		order.push_back(v);
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T)
{
	vector<int>PP(N);
	iota(PP.begin(), PP.end(), 0);
	shuffle(PP.begin(), PP.end(), rng);
	for (int i = 0; i < M; i++)
	{
		adj[A[i]].push_back(B[i]);
		adj[B[i]].push_back(A[i]);
	}
	for (int i = 0; i < N; i++)
		shuffle(adj[i].begin(), adj[i].end(), rng);
	dfs(rng() % N);
	ll X = 0;
	vector<int>stak = {P};
	set<int>bitai;
	set<int>aplankyti;
	int ii = find(order.begin(), order.end(), P) - order.begin();
	while (true)
	{
		X |= V * (1ll << bitas[P]);
		bitai.insert(bitas[P]);
		aplankyti.insert(P);
		if (bitai.size() == 60)
			break;
		while (order[ii] == P)
		{
			ii = (ii - 1 + order.size()) % order.size();
		}
		int v1 = order[ii];
		V = Move(v1);
		P = v1;
	}
	return X;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1408 KB Output is correct
2 Correct 4 ms 1404 KB Output is correct
3 Correct 6 ms 1664 KB Output is correct
4 Correct 4 ms 1404 KB Output is correct
5 Correct 4 ms 1464 KB Output is correct
6 Correct 4 ms 1388 KB Output is correct
7 Correct 5 ms 1424 KB Output is correct
8 Correct 6 ms 1540 KB Output is correct
9 Correct 6 ms 1540 KB Output is correct
10 Correct 4 ms 1408 KB Output is correct
11 Correct 9 ms 1996 KB Output is correct
12 Correct 4 ms 1464 KB Output is correct
13 Correct 5 ms 1408 KB Output is correct
14 Correct 6 ms 1428 KB Output is correct
15 Correct 6 ms 1440 KB Output is correct
16 Correct 6 ms 1424 KB Output is correct
17 Correct 6 ms 1532 KB Output is correct
18 Correct 6 ms 1480 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 7708 KB Output is correct
2 Correct 72 ms 7720 KB Output is correct
3 Correct 76 ms 7708 KB Output is correct
4 Correct 46 ms 6132 KB Output is correct
5 Correct 53 ms 7064 KB Output is correct
6 Correct 49 ms 6396 KB Output is correct
7 Correct 47 ms 6304 KB Output is correct
8 Correct 47 ms 6436 KB Output is correct
9 Correct 47 ms 6516 KB Output is correct
10 Correct 44 ms 6040 KB Output is correct
11 Correct 45 ms 6268 KB Output is correct
12 Correct 42 ms 5684 KB Output is correct
13 Correct 41 ms 5720 KB Output is correct
14 Correct 43 ms 5880 KB Output is correct
15 Correct 45 ms 6152 KB Output is correct
16 Correct 45 ms 5912 KB Output is correct
17 Correct 46 ms 6048 KB Output is correct
18 Correct 46 ms 6040 KB Output is correct
19 Correct 45 ms 6176 KB Output is correct
20 Correct 28 ms 6456 KB Output is correct
21 Correct 30 ms 6564 KB Output is correct
22 Correct 48 ms 6440 KB Output is correct
23 Correct 48 ms 6456 KB Output is correct
24 Correct 46 ms 6308 KB Output is correct
25 Correct 47 ms 6612 KB Output is correct
26 Correct 47 ms 6424 KB Output is correct
27 Correct 47 ms 6432 KB Output is correct
28 Correct 47 ms 6616 KB Output is correct
29 Correct 42 ms 6100 KB Output is correct
30 Correct 45 ms 6060 KB Output is correct
31 Correct 4 ms 1452 KB Output is correct
32 Correct 4 ms 1480 KB Output is correct
33 Correct 5 ms 1404 KB Output is correct
34 Correct 4 ms 1272 KB Output is correct
35 Correct 4 ms 1504 KB Output is correct
36 Correct 5 ms 1460 KB Output is correct
37 Correct 5 ms 1404 KB Output is correct
38 Correct 5 ms 1396 KB Output is correct
39 Correct 5 ms 1476 KB Output is correct
40 Correct 5 ms 1396 KB Output is correct
41 Correct 5 ms 1396 KB Output is correct
42 Correct 4 ms 1396 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1272 KB Output is correct
2 Correct 5 ms 1464 KB Output is correct
3 Correct 4 ms 1396 KB Output is correct
4 Correct 9 ms 2080 KB Output is correct
5 Correct 9 ms 2256 KB Output is correct
6 Correct 8 ms 2212 KB Output is correct
7 Correct 9 ms 2208 KB Output is correct
8 Correct 9 ms 2232 KB Output is correct
9 Correct 32 ms 6860 KB Output is correct
10 Correct 34 ms 6792 KB Output is correct
11 Correct 28 ms 6752 KB Output is correct
12 Correct 4 ms 1396 KB Output is correct
13 Correct 4 ms 1404 KB Output is correct
14 Correct 4 ms 1276 KB Output is correct
15 Correct 4 ms 1344 KB Output is correct

Subtask #4
44.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 7600 KB Output is correct
2 Correct 75 ms 7764 KB Output is correct
3 Correct 74 ms 7704 KB Output is correct
4 Correct 46 ms 6140 KB Output is correct
5 Correct 50 ms 6668 KB Output is correct
6 Correct 49 ms 6556 KB Output is correct
7 Correct 50 ms 6304 KB Output is correct
8 Correct 46 ms 6576 KB Output is correct
9 Correct 47 ms 6296 KB Output is correct
10 Partially correct 48 ms 6052 KB Partially correct
11 Correct 48 ms 6204 KB Output is correct
12 Partially correct 42 ms 5720 KB Partially correct
13 Correct 45 ms 5564 KB Output is correct
14 Correct 47 ms 5984 KB Output is correct
15 Partially correct 49 ms 6024 KB Partially correct
16 Correct 48 ms 5920 KB Output is correct
17 Correct 51 ms 6136 KB Output is correct
18 Correct 49 ms 6176 KB Output is correct
19 Correct 47 ms 6140 KB Output is correct
20 Correct 30 ms 6524 KB Output is correct
21 Partially correct 31 ms 6432 KB Partially correct
22 Correct 52 ms 6424 KB Output is correct
23 Correct 51 ms 6320 KB Output is correct
24 Correct 48 ms 6492 KB Output is correct
25 Correct 51 ms 6576 KB Output is correct
26 Correct 49 ms 6436 KB Output is correct
27 Correct 51 ms 6628 KB Output is correct
28 Correct 47 ms 6424 KB Output is correct
29 Partially correct 43 ms 6180 KB Partially correct
30 Correct 44 ms 6416 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 7564 KB Output is correct
2 Correct 70 ms 7660 KB Output is correct
3 Correct 68 ms 7680 KB Output is correct
4 Incorrect 45 ms 6144 KB Output isn't correct
5 Halted 0 ms 0 KB -