oj.uz

Submission #108524

# Submission time Handle Problem Language Result Execution time Memory
108524 2019-04-30T06:39:46 Z E869120 Amusement Park (JOI17_amusement_park) C++14
83 / 100
 1132 ms 4340 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 = 2804;
	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 = 2804;
	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 48 ms 1152 KB Output is correct
2 Correct 52 ms 1348 KB Output is correct
3 Correct 50 ms 1336 KB Output is correct
4 Correct 51 ms 1232 KB Output is correct
5 Correct 50 ms 1284 KB Output is correct
6 Correct 53 ms 1268 KB Output is correct
7 Correct 53 ms 1404 KB Output is correct
8 Correct 55 ms 1392 KB Output is correct
9 Correct 47 ms 1416 KB Output is correct
10 Correct 58 ms 1268 KB Output is correct
11 Correct 71 ms 1680 KB Output is correct
12 Correct 50 ms 1344 KB Output is correct
13 Correct 58 ms 1292 KB Output is correct
14 Correct 50 ms 1276 KB Output is correct
15 Correct 57 ms 1376 KB Output is correct
16 Correct 60 ms 1268 KB Output is correct
17 Correct 57 ms 1416 KB Output is correct
18 Correct 49 ms 1320 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1087 ms 4300 KB Output is correct
2 Correct 1119 ms 4340 KB Output is correct
3 Correct 979 ms 4312 KB Output is correct
4 Correct 731 ms 3076 KB Output is correct
5 Correct 937 ms 3316 KB Output is correct
6 Correct 813 ms 3240 KB Output is correct
7 Correct 961 ms 3000 KB Output is correct
8 Correct 874 ms 3236 KB Output is correct
9 Correct 777 ms 3236 KB Output is correct
10 Correct 486 ms 3084 KB Output is correct
11 Correct 436 ms 3076 KB Output is correct
12 Correct 534 ms 2784 KB Output is correct
13 Correct 611 ms 2760 KB Output is correct
14 Correct 548 ms 2992 KB Output is correct
15 Correct 685 ms 3044 KB Output is correct
16 Correct 647 ms 2920 KB Output is correct
17 Correct 714 ms 3024 KB Output is correct
18 Correct 706 ms 3032 KB Output is correct
19 Correct 684 ms 2948 KB Output is correct
20 Correct 486 ms 3304 KB Output is correct
21 Correct 474 ms 3296 KB Output is correct
22 Correct 588 ms 3112 KB Output is correct
23 Correct 546 ms 3220 KB Output is correct
24 Correct 585 ms 3124 KB Output is correct
25 Correct 579 ms 3220 KB Output is correct
26 Correct 622 ms 3416 KB Output is correct
27 Correct 725 ms 3284 KB Output is correct
28 Correct 672 ms 3308 KB Output is correct
29 Correct 684 ms 3036 KB Output is correct
30 Correct 539 ms 3160 KB Output is correct
31 Correct 49 ms 1220 KB Output is correct
32 Correct 52 ms 1280 KB Output is correct
33 Correct 63 ms 1408 KB Output is correct
34 Correct 54 ms 1392 KB Output is correct
35 Correct 54 ms 1256 KB Output is correct
36 Correct 52 ms 1416 KB Output is correct
37 Correct 51 ms 1332 KB Output is correct
38 Correct 49 ms 1244 KB Output is correct
39 Correct 53 ms 1260 KB Output is correct
40 Correct 54 ms 1244 KB Output is correct
41 Correct 52 ms 1360 KB Output is correct
42 Correct 52 ms 1260 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 1304 KB Output is correct
2 Correct 45 ms 1264 KB Output is correct
3 Correct 47 ms 1160 KB Output is correct
4 Correct 104 ms 1656 KB Output is correct
5 Correct 89 ms 1704 KB Output is correct
6 Correct 89 ms 1676 KB Output is correct
7 Correct 107 ms 1564 KB Output is correct
8 Correct 90 ms 1704 KB Output is correct
9 Correct 493 ms 3612 KB Output is correct
10 Correct 630 ms 3592 KB Output is correct
11 Correct 641 ms 3504 KB Output is correct
12 Correct 53 ms 1288 KB Output is correct
13 Correct 56 ms 1376 KB Output is correct
14 Correct 49 ms 1408 KB Output is correct
15 Correct 52 ms 1152 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1020 ms 4048 KB Output is correct
2 Correct 1132 ms 4136 KB Output is correct
3 Correct 987 ms 4136 KB Output is correct
4 Correct 790 ms 2948 KB Output is correct
5 Correct 931 ms 3324 KB Output is correct
6 Correct 885 ms 3096 KB Output is correct
7 Correct 739 ms 3120 KB Output is correct
8 Correct 715 ms 2952 KB Output is correct
9 Correct 742 ms 2976 KB Output is correct
10 Correct 464 ms 3096 KB Output is correct
11 Correct 377 ms 3120 KB Output is correct
12 Correct 519 ms 2724 KB Output is correct
13 Correct 488 ms 2720 KB Output is correct
14 Correct 505 ms 2900 KB Output is correct
15 Correct 673 ms 2864 KB Output is correct
16 Correct 665 ms 2948 KB Output is correct
17 Correct 645 ms 2976 KB Output is correct
18 Correct 702 ms 2772 KB Output is correct
19 Correct 734 ms 2864 KB Output is correct
20 Correct 525 ms 3328 KB Output is correct
21 Correct 395 ms 3264 KB Output is correct
22 Correct 581 ms 3216 KB Output is correct
23 Correct 632 ms 3044 KB Output is correct
24 Correct 522 ms 2984 KB Output is correct
25 Correct 509 ms 3004 KB Output is correct
26 Correct 652 ms 3004 KB Output is correct
27 Correct 600 ms 3252 KB Output is correct
28 Correct 616 ms 2928 KB Output is correct
29 Correct 569 ms 3004 KB Output is correct
30 Correct 599 ms 3056 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1061 ms 4148 KB Output is correct
2 Correct 935 ms 4272 KB Output is correct
3 Correct 1095 ms 4108 KB Output is correct
4 Correct 698 ms 2860 KB Output is correct
5 Correct 899 ms 3360 KB Output is correct
6 Correct 862 ms 3128 KB Output is correct
7 Correct 842 ms 3008 KB Output is correct
8 Correct 776 ms 3208 KB Output is correct
9 Correct 719 ms 3092 KB Output is correct
10 Correct 431 ms 2964 KB Output is correct
11 Correct 395 ms 2912 KB Output is correct
12 Correct 453 ms 2720 KB Output is correct
13 Correct 531 ms 2820 KB Output is correct
14 Correct 562 ms 2924 KB Output is correct
15 Correct 644 ms 2892 KB Output is correct
16 Correct 658 ms 2812 KB Output is correct
17 Correct 758 ms 2900 KB Output is correct
18 Correct 735 ms 2904 KB Output is correct
19 Correct 642 ms 3080 KB Output is correct
20 Correct 517 ms 3436 KB Output is correct
21 Correct 454 ms 3288 KB Output is correct
22 Correct 569 ms 3344 KB Output is correct
23 Correct 566 ms 3320 KB Output is correct
24 Correct 553 ms 3312 KB Output is correct
25 Correct 578 ms 3380 KB Output is correct
26 Incorrect 603 ms 3164 KB Output isn't correct
27 Halted 0 ms 0 KB -