oj.uz

Submission #108531

# Submission time Handle Problem Language Result Execution time Memory
108531 2019-04-30T06:44:45 Z E869120 Amusement Park (JOI17_amusement_park) C++14
82 / 100
 1148 ms 4292 KB 
#include "Joi.h"
#include <iostream>
#include <vector>
using namespace std;

vector<int>G[10009]; int col[10009], v[20009], cnts;

void make_ransuu1(int B) {
	for (int i = 0; i < B; i++) v[i] = i;

	unsigned long long x = 1333;
	for (int i = 0; i < 1000000; i++) {
		x ^= x << 13;
		x ^= x >> 7;
		x ^= x << 17;
		int u1 = (x % B);
		x ^= x << 13;
		x ^= x >> 7;
		x ^= x << 17;
		int u2 = (x % B);
		swap(v[u1], v[u2]);
	}
}

void dfs(int pos) {
	if (col[pos] >= 0) return;
	col[pos] = cnts % 60; cnts++;
	for (int i = 0; i < G[pos].size(); i++) dfs(G[pos][i]);
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
	make_ransuu1(M);
	for (int i = 0; i < M; i++) { G[A[v[i]]].push_back(B[v[i]]); G[B[v[i]]].push_back(A[v[i]]); }
	for (int i = 0; i < N; i++) col[i] = -1;
	dfs(0);
	for (int i = 0; i < N; i++) MessageBoard(i, (X / (1LL << col[i])) % 2);
}

#include "Ioi.h"
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

vector<int>I[10009]; int dist[10009], par[10009], cols[10009], vv[20009], cntv;
int N, M; bool used[60];

void make_ransuu2(int B) {
	for (int i = 0; i < B; i++) vv[i] = i;

	unsigned long long x = 1333;
	for (int i = 0; i < 1000000; i++) {
		x ^= x << 13;
		x ^= x >> 7;
		x ^= x << 17;
		int u1 = (x % B);
		x ^= x << 13;
		x ^= x >> 7;
		x ^= x << 17;
		int u2 = (x % B);
		swap(vv[u1], vv[u2]);
	}
}


void dfs2(int pos) {
	if (cols[pos] >= 0) return;
	cols[pos] = cntv % 60; cntv++;
	for (int i = 0; i < I[pos].size(); i++) dfs2(I[pos][i]);
}

vector<int> nearest(int sta, int rem) {
	for (int i = 0; i < N; i++) dist[i] = (1 << 30);
	
	queue<int>Q; Q.push(sta); dist[sta] = 0;
	while (!Q.empty()) {
		int pos = Q.front(); Q.pop();
		for (int i = 0; i < I[pos].size(); i++) {
			int to = I[pos][i];
			if (dist[to] > dist[pos] + 1) {
				dist[to] = dist[pos] + 1;
				par[to] = pos;
				Q.push(to);
			}
		}
	}

	int id = 0, minx = 10000;
	for (int i = 0; i < N; i++) {
		if (cols[i] == rem && dist[i] < minx) {
			minx = dist[i]; id = i;
		}
	}

	vector<int>U;
	while (true) {
		U.push_back(id); if (id == sta) break;
		id = par[id];
	}
	reverse(U.begin(), U.end());
	return U;
}

long long Ioi(int NN, int MM, int A[], int B[], int P, int V, int T) {
	N = NN; M = MM; make_ransuu2(M);
	for (int i = 0; i < M; i++) { I[A[vv[i]]].push_back(B[vv[i]]); I[B[vv[i]]].push_back(A[vv[i]]); }
	for (int i = 0; i < N; i++) cols[i] = -1;
	dfs2(0);
	
	int cx = P; long long rem = 0;
	for (int i = 0; i < 60; i++) {
		vector<int>E; int id = -1;
		for (int j = 0; j < 60; j++) {
			if (used[j] == true) continue;
			vector<int>F = nearest(cx, j);
			if (E.size() == 0 || E.size() > F.size()) { E = F; id = j; }
		}
		int F = V;
		for (int j = 1; j < E.size(); j++) {
			F = Move(E[j]);
		}
		rem += 1LL * F * (1LL << id);
		if (E.size() >= 1) cx = E[E.size() - 1];
		used[id] = true;
	}
	return rem;
}

Compilation message

Joi.cpp: In function 'void dfs(int)':
Joi.cpp:28:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < G[pos].size(); i++) dfs(G[pos][i]);
                  ~~^~~~~~~~~~~~~~~

Ioi.cpp: In function 'void dfs2(int)':
Ioi.cpp:31:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < I[pos].size(); i++) dfs2(I[pos][i]);
                  ~~^~~~~~~~~~~~~~~
Ioi.cpp: In function 'std::vector<int> nearest(int, int)':
Ioi.cpp:40:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < I[pos].size(); i++) {
                   ~~^~~~~~~~~~~~~~~
Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:81:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 1; j < E.size(); j++) {
                   ~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 1152 KB Output is correct
2 Correct 44 ms 1152 KB Output is correct
3 Correct 46 ms 1284 KB Output is correct
4 Correct 50 ms 1244 KB Output is correct
5 Correct 44 ms 1392 KB Output is correct
6 Correct 48 ms 1236 KB Output is correct
7 Correct 59 ms 1276 KB Output is correct
8 Correct 52 ms 1372 KB Output is correct
9 Correct 49 ms 1284 KB Output is correct
10 Correct 48 ms 1288 KB Output is correct
11 Correct 81 ms 1584 KB Output is correct
12 Correct 51 ms 1280 KB Output is correct
13 Correct 61 ms 1284 KB Output is correct
14 Correct 55 ms 1392 KB Output is correct
15 Correct 52 ms 1284 KB Output is correct
16 Correct 59 ms 1396 KB Output is correct
17 Correct 51 ms 1364 KB Output is correct
18 Correct 54 ms 1412 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1037 ms 4292 KB Output is correct
2 Correct 938 ms 4036 KB Output is correct
3 Correct 1121 ms 4052 KB Output is correct
4 Correct 706 ms 2856 KB Output is correct
5 Correct 902 ms 3024 KB Output is correct
6 Correct 772 ms 3056 KB Output is correct
7 Correct 822 ms 3072 KB Output is correct
8 Correct 810 ms 3100 KB Output is correct
9 Correct 928 ms 3112 KB Output is correct
10 Correct 510 ms 3080 KB Output is correct
11 Correct 509 ms 3044 KB Output is correct
12 Correct 503 ms 2652 KB Output is correct
13 Correct 488 ms 2788 KB Output is correct
14 Correct 566 ms 2776 KB Output is correct
15 Correct 616 ms 2792 KB Output is correct
16 Correct 654 ms 2928 KB Output is correct
17 Correct 765 ms 2772 KB Output is correct
18 Correct 809 ms 2992 KB Output is correct
19 Correct 686 ms 2996 KB Output is correct
20 Correct 512 ms 3260 KB Output is correct
21 Correct 492 ms 3252 KB Output is correct
22 Correct 588 ms 3052 KB Output is correct
23 Correct 550 ms 3120 KB Output is correct
24 Correct 570 ms 3072 KB Output is correct
25 Correct 576 ms 3084 KB Output is correct
26 Correct 611 ms 3096 KB Output is correct
27 Correct 542 ms 3084 KB Output is correct
28 Correct 652 ms 3160 KB Output is correct
29 Correct 494 ms 2860 KB Output is correct
30 Correct 479 ms 3024 KB Output is correct
31 Correct 45 ms 1152 KB Output is correct
32 Correct 47 ms 1184 KB Output is correct
33 Correct 54 ms 1292 KB Output is correct
34 Correct 52 ms 1408 KB Output is correct
35 Correct 51 ms 1236 KB Output is correct
36 Correct 53 ms 1280 KB Output is correct
37 Correct 54 ms 1288 KB Output is correct
38 Correct 54 ms 1280 KB Output is correct
39 Correct 51 ms 1244 KB Output is correct
40 Correct 49 ms 1240 KB Output is correct
41 Correct 46 ms 1172 KB Output is correct
42 Correct 52 ms 1152 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 1144 KB Output is correct
2 Correct 56 ms 1252 KB Output is correct
3 Correct 50 ms 1152 KB Output is correct
4 Correct 100 ms 1804 KB Output is correct
5 Correct 105 ms 1676 KB Output is correct
6 Correct 95 ms 1548 KB Output is correct
7 Correct 102 ms 1808 KB Output is correct
8 Correct 95 ms 1708 KB Output is correct
9 Correct 520 ms 3620 KB Output is correct
10 Correct 622 ms 3512 KB Output is correct
11 Correct 568 ms 3504 KB Output is correct
12 Correct 51 ms 1152 KB Output is correct
13 Correct 48 ms 1144 KB Output is correct
14 Correct 57 ms 1288 KB Output is correct
15 Correct 43 ms 1392 KB Output is correct

Subtask #4
54.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 997 ms 4208 KB Output is correct
2 Correct 1029 ms 4020 KB Output is correct
3 Correct 1030 ms 4132 KB Output is correct
4 Correct 722 ms 2976 KB Output is correct
5 Correct 940 ms 3400 KB Output is correct
6 Correct 755 ms 3284 KB Output is correct
7 Correct 798 ms 3012 KB Output is correct
8 Correct 805 ms 3128 KB Output is correct
9 Correct 821 ms 3068 KB Output is correct
10 Correct 468 ms 2992 KB Output is correct
11 Correct 421 ms 3000 KB Output is correct
12 Correct 535 ms 2892 KB Output is correct
13 Correct 466 ms 2732 KB Output is correct
14 Correct 508 ms 2868 KB Output is correct
15 Correct 656 ms 2932 KB Output is correct
16 Correct 566 ms 3000 KB Output is correct
17 Correct 743 ms 2864 KB Output is correct
18 Correct 660 ms 3000 KB Output is correct
19 Correct 742 ms 2960 KB Output is correct
20 Partially correct 480 ms 3252 KB Partially correct
21 Correct 457 ms 3256 KB Output is correct
22 Correct 546 ms 3128 KB Output is correct
23 Correct 572 ms 3132 KB Output is correct
24 Correct 547 ms 3196 KB Output is correct
25 Correct 554 ms 3128 KB Output is correct
26 Correct 683 ms 3124 KB Output is correct
27 Correct 623 ms 3248 KB Output is correct
28 Correct 559 ms 3172 KB Output is correct
29 Correct 535 ms 3008 KB Output is correct
30 Correct 564 ms 3244 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1051 ms 4128 KB Output is correct
2 Correct 1082 ms 4284 KB Output is correct
3 Correct 1148 ms 4056 KB Output is correct
4 Correct 678 ms 3088 KB Output is correct
5 Correct 904 ms 3516 KB Output is correct
6 Correct 801 ms 3272 KB Output is correct
7 Correct 791 ms 3144 KB Output is correct
8 Correct 742 ms 3376 KB Output is correct
9 Correct 730 ms 3120 KB Output is correct
10 Correct 442 ms 2928 KB Output is correct
11 Correct 437 ms 3000 KB Output is correct
12 Correct 490 ms 2720 KB Output is correct
13 Correct 469 ms 2800 KB Output is correct
14 Correct 493 ms 2752 KB Output is correct
15 Correct 775 ms 2992 KB Output is correct
16 Incorrect 651 ms 2768 KB Output isn't correct
17 Halted 0 ms 0 KB -