oj.uz

Submission #108533

# Submission time Handle Problem Language Result Execution time Memory
108533 2019-04-30T06:47:38 Z E869120 Amusement Park (JOI17_amusement_park) C++14
82 / 100
 1047 ms 4248 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 = 1999;
	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 = 1999;
	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 42 ms 1196 KB Output is correct
2 Correct 53 ms 1240 KB Output is correct
3 Correct 51 ms 1352 KB Output is correct
4 Correct 48 ms 1388 KB Output is correct
5 Correct 56 ms 1152 KB Output is correct
6 Correct 60 ms 1152 KB Output is correct
7 Correct 49 ms 1288 KB Output is correct
8 Correct 63 ms 1404 KB Output is correct
9 Correct 51 ms 1412 KB Output is correct
10 Correct 49 ms 1288 KB Output is correct
11 Correct 73 ms 1584 KB Output is correct
12 Correct 54 ms 1144 KB Output is correct
13 Correct 47 ms 1316 KB Output is correct
14 Correct 49 ms 1212 KB Output is correct
15 Correct 49 ms 1292 KB Output is correct
16 Correct 51 ms 1404 KB Output is correct
17 Correct 50 ms 1284 KB Output is correct
18 Correct 52 ms 1292 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1047 ms 4100 KB Output is correct
2 Correct 985 ms 4136 KB Output is correct
3 Correct 1037 ms 4056 KB Output is correct
4 Correct 685 ms 2860 KB Output is correct
5 Correct 859 ms 3028 KB Output is correct
6 Correct 813 ms 2984 KB Output is correct
7 Correct 853 ms 3220 KB Output is correct
8 Correct 769 ms 3004 KB Output is correct
9 Correct 761 ms 3120 KB Output is correct
10 Correct 429 ms 3052 KB Output is correct
11 Correct 386 ms 2960 KB Output is correct
12 Correct 431 ms 2656 KB Output is correct
13 Correct 460 ms 2712 KB Output is correct
14 Correct 476 ms 2828 KB Output is correct
15 Correct 717 ms 3128 KB Output is correct
16 Correct 664 ms 2864 KB Output is correct
17 Correct 722 ms 3000 KB Output is correct
18 Correct 754 ms 2992 KB Output is correct
19 Correct 684 ms 2864 KB Output is correct
20 Correct 429 ms 3272 KB Output is correct
21 Correct 583 ms 3136 KB Output is correct
22 Correct 628 ms 3028 KB Output is correct
23 Correct 556 ms 3004 KB Output is correct
24 Correct 528 ms 2976 KB Output is correct
25 Correct 567 ms 3080 KB Output is correct
26 Correct 637 ms 3136 KB Output is correct
27 Correct 648 ms 3392 KB Output is correct
28 Correct 526 ms 3104 KB Output is correct
29 Correct 520 ms 2928 KB Output is correct
30 Correct 530 ms 3024 KB Output is correct
31 Correct 55 ms 1288 KB Output is correct
32 Correct 46 ms 1256 KB Output is correct
33 Correct 53 ms 1292 KB Output is correct
34 Correct 50 ms 1288 KB Output is correct
35 Correct 51 ms 1388 KB Output is correct
36 Correct 49 ms 1300 KB Output is correct
37 Correct 57 ms 1272 KB Output is correct
38 Correct 45 ms 1340 KB Output is correct
39 Correct 47 ms 1244 KB Output is correct
40 Correct 48 ms 1272 KB Output is correct
41 Correct 45 ms 1328 KB Output is correct
42 Correct 50 ms 1280 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 1336 KB Output is correct
2 Correct 47 ms 1152 KB Output is correct
3 Correct 51 ms 1528 KB Output is correct
4 Correct 106 ms 1668 KB Output is correct
5 Correct 98 ms 1672 KB Output is correct
6 Correct 97 ms 1596 KB Output is correct
7 Correct 111 ms 1660 KB Output is correct
8 Correct 93 ms 1652 KB Output is correct
9 Correct 496 ms 3508 KB Output is correct
10 Correct 701 ms 3476 KB Output is correct
11 Correct 588 ms 3512 KB Output is correct
12 Correct 46 ms 1236 KB Output is correct
13 Correct 47 ms 1340 KB Output is correct
14 Correct 43 ms 1152 KB Output is correct
15 Correct 46 ms 1200 KB Output is correct

Subtask #4
54.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 963 ms 4188 KB Output is correct
2 Correct 917 ms 4096 KB Output is correct
3 Correct 1032 ms 4248 KB Output is correct
4 Correct 709 ms 2872 KB Output is correct
5 Correct 984 ms 3248 KB Output is correct
6 Correct 806 ms 3196 KB Output is correct
7 Correct 855 ms 3168 KB Output is correct
8 Correct 748 ms 2992 KB Output is correct
9 Correct 764 ms 3076 KB Output is correct
10 Correct 484 ms 2984 KB Output is correct
11 Correct 458 ms 3120 KB Output is correct
12 Correct 437 ms 2800 KB Output is correct
13 Correct 511 ms 2792 KB Output is correct
14 Correct 489 ms 2956 KB Output is correct
15 Correct 626 ms 2864 KB Output is correct
16 Correct 601 ms 2872 KB Output is correct
17 Correct 696 ms 2988 KB Output is correct
18 Correct 699 ms 3000 KB Output is correct
19 Partially correct 668 ms 2772 KB Partially correct
20 Correct 425 ms 3120 KB Output is correct
21 Correct 417 ms 3280 KB Output is correct
22 Correct 533 ms 3136 KB Output is correct
23 Correct 601 ms 3336 KB Output is correct
24 Correct 617 ms 2976 KB Output is correct
25 Correct 703 ms 3184 KB Output is correct
26 Correct 667 ms 3172 KB Output is correct
27 Correct 622 ms 3028 KB Output is correct
28 Correct 598 ms 2912 KB Output is correct
29 Correct 529 ms 3016 KB Output is correct
30 Correct 492 ms 3056 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 986 ms 4096 KB Output is correct
2 Correct 1028 ms 4184 KB Output is correct
3 Correct 1036 ms 4184 KB Output is correct
4 Correct 755 ms 2904 KB Output is correct
5 Correct 896 ms 3440 KB Output is correct
6 Correct 722 ms 3076 KB Output is correct
7 Correct 811 ms 2964 KB Output is correct
8 Correct 743 ms 3112 KB Output is correct
9 Correct 806 ms 3176 KB Output is correct
10 Correct 414 ms 2968 KB Output is correct
11 Correct 414 ms 3028 KB Output is correct
12 Correct 433 ms 2728 KB Output is correct
13 Correct 454 ms 2800 KB Output is correct
14 Correct 456 ms 2744 KB Output is correct
15 Correct 691 ms 2864 KB Output is correct
16 Correct 654 ms 2984 KB Output is correct
17 Correct 740 ms 2896 KB Output is correct
18 Correct 736 ms 2944 KB Output is correct
19 Correct 800 ms 2968 KB Output is correct
20 Correct 479 ms 3148 KB Output is correct
21 Correct 622 ms 3248 KB Output is correct
22 Correct 591 ms 2996 KB Output is correct
23 Correct 597 ms 2992 KB Output is correct
24 Correct 596 ms 3212 KB Output is correct
25 Correct 525 ms 3088 KB Output is correct
26 Correct 555 ms 3056 KB Output is correct
27 Correct 606 ms 3176 KB Output is correct
28 Correct 556 ms 3108 KB Output is correct
29 Correct 497 ms 3168 KB Output is correct
30 Correct 584 ms 3160 KB Output is correct
31 Correct 53 ms 1416 KB Output is correct
32 Correct 69 ms 1148 KB Output is correct
33 Correct 60 ms 1452 KB Output is correct
34 Correct 56 ms 1384 KB Output is correct
35 Correct 52 ms 1456 KB Output is correct
36 Correct 49 ms 1144 KB Output is correct
37 Correct 50 ms 1144 KB Output is correct
38 Correct 48 ms 1408 KB Output is correct
39 Correct 51 ms 1232 KB Output is correct
40 Incorrect 57 ms 1244 KB Output isn't correct
41 Halted 0 ms 0 KB -