oj.uz

Submission #108522

# Submission time Handle Problem Language Result Execution time Memory
108522 2019-04-30T06:39:10 Z E869120 Amusement Park (JOI17_amusement_park) C++14
83 / 100
 1200 ms 4520 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 = 2018;
	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 = 2018;
	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 49 ms 1152 KB Output is correct
2 Correct 45 ms 1152 KB Output is correct
3 Correct 57 ms 1276 KB Output is correct
4 Correct 56 ms 1152 KB Output is correct
5 Correct 54 ms 1372 KB Output is correct
6 Correct 50 ms 1144 KB Output is correct
7 Correct 53 ms 1284 KB Output is correct
8 Correct 53 ms 1404 KB Output is correct
9 Correct 51 ms 1276 KB Output is correct
10 Correct 45 ms 1152 KB Output is correct
11 Correct 83 ms 1572 KB Output is correct
12 Correct 61 ms 1152 KB Output is correct
13 Correct 55 ms 1376 KB Output is correct
14 Correct 63 ms 1260 KB Output is correct
15 Correct 62 ms 1404 KB Output is correct
16 Correct 57 ms 1292 KB Output is correct
17 Correct 57 ms 1276 KB Output is correct
18 Correct 54 ms 1396 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1034 ms 4128 KB Output is correct
2 Correct 1048 ms 4180 KB Output is correct
3 Correct 1112 ms 4080 KB Output is correct
4 Correct 786 ms 2900 KB Output is correct
5 Correct 940 ms 3160 KB Output is correct
6 Correct 810 ms 2984 KB Output is correct
7 Correct 774 ms 3080 KB Output is correct
8 Correct 848 ms 3144 KB Output is correct
9 Correct 827 ms 3072 KB Output is correct
10 Correct 389 ms 3016 KB Output is correct
11 Correct 426 ms 3056 KB Output is correct
12 Correct 432 ms 2752 KB Output is correct
13 Correct 479 ms 2796 KB Output is correct
14 Correct 578 ms 2748 KB Output is correct
15 Correct 608 ms 2864 KB Output is correct
16 Correct 698 ms 2988 KB Output is correct
17 Correct 686 ms 2988 KB Output is correct
18 Correct 761 ms 3004 KB Output is correct
19 Correct 783 ms 2812 KB Output is correct
20 Correct 436 ms 3124 KB Output is correct
21 Correct 420 ms 3248 KB Output is correct
22 Correct 583 ms 3120 KB Output is correct
23 Correct 540 ms 3012 KB Output is correct
24 Correct 522 ms 3088 KB Output is correct
25 Correct 540 ms 3116 KB Output is correct
26 Correct 541 ms 3128 KB Output is correct
27 Correct 546 ms 3148 KB Output is correct
28 Correct 626 ms 3220 KB Output is correct
29 Correct 485 ms 2936 KB Output is correct
30 Correct 612 ms 2936 KB Output is correct
31 Correct 52 ms 1372 KB Output is correct
32 Correct 48 ms 1152 KB Output is correct
33 Correct 52 ms 1368 KB Output is correct
34 Correct 51 ms 1388 KB Output is correct
35 Correct 46 ms 1152 KB Output is correct
36 Correct 49 ms 1288 KB Output is correct
37 Correct 46 ms 1304 KB Output is correct
38 Correct 46 ms 1372 KB Output is correct
39 Correct 49 ms 1236 KB Output is correct
40 Correct 47 ms 1536 KB Output is correct
41 Correct 51 ms 1252 KB Output is correct
42 Correct 44 ms 1248 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 1152 KB Output is correct
2 Correct 49 ms 1380 KB Output is correct
3 Correct 63 ms 1372 KB Output is correct
4 Correct 111 ms 1656 KB Output is correct
5 Correct 95 ms 1648 KB Output is correct
6 Correct 129 ms 1624 KB Output is correct
7 Correct 96 ms 1588 KB Output is correct
8 Correct 136 ms 1704 KB Output is correct
9 Correct 497 ms 3432 KB Output is correct
10 Correct 615 ms 3460 KB Output is correct
11 Correct 673 ms 3476 KB Output is correct
12 Correct 56 ms 1312 KB Output is correct
13 Correct 47 ms 1376 KB Output is correct
14 Correct 53 ms 1332 KB Output is correct
15 Correct 51 ms 1276 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1083 ms 4372 KB Output is correct
2 Correct 1059 ms 4340 KB Output is correct
3 Correct 1200 ms 4452 KB Output is correct
4 Correct 794 ms 3044 KB Output is correct
5 Correct 923 ms 3392 KB Output is correct
6 Correct 823 ms 3240 KB Output is correct
7 Correct 782 ms 3248 KB Output is correct
8 Correct 817 ms 3024 KB Output is correct
9 Correct 850 ms 3120 KB Output is correct
10 Correct 460 ms 3104 KB Output is correct
11 Correct 427 ms 3120 KB Output is correct
12 Correct 547 ms 2884 KB Output is correct
13 Correct 588 ms 2840 KB Output is correct
14 Correct 491 ms 2888 KB Output is correct
15 Correct 691 ms 3052 KB Output is correct
16 Correct 685 ms 3036 KB Output is correct
17 Correct 707 ms 3168 KB Output is correct
18 Correct 781 ms 3032 KB Output is correct
19 Correct 679 ms 2984 KB Output is correct
20 Correct 481 ms 3216 KB Output is correct
21 Correct 464 ms 3288 KB Output is correct
22 Correct 530 ms 3188 KB Output is correct
23 Correct 588 ms 3284 KB Output is correct
24 Correct 520 ms 3216 KB Output is correct
25 Correct 587 ms 3208 KB Output is correct
26 Correct 584 ms 3272 KB Output is correct
27 Correct 586 ms 3300 KB Output is correct
28 Correct 528 ms 3196 KB Output is correct
29 Correct 547 ms 3048 KB Output is correct
30 Correct 566 ms 3136 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 965 ms 4352 KB Output is correct
2 Correct 1075 ms 4520 KB Output is correct
3 Correct 1045 ms 4412 KB Output is correct
4 Correct 681 ms 3072 KB Output is correct
5 Correct 1035 ms 3532 KB Output is correct
6 Correct 828 ms 3268 KB Output is correct
7 Correct 864 ms 3164 KB Output is correct
8 Correct 788 ms 3376 KB Output is correct
9 Correct 752 ms 3252 KB Output is correct
10 Correct 506 ms 3204 KB Output is correct
11 Correct 385 ms 3124 KB Output is correct
12 Correct 513 ms 2888 KB Output is correct
13 Correct 526 ms 2984 KB Output is correct
14 Correct 449 ms 3048 KB Output is correct
15 Correct 773 ms 3008 KB Output is correct
16 Correct 688 ms 2964 KB Output is correct
17 Correct 848 ms 3044 KB Output is correct
18 Incorrect 756 ms 3036 KB Output isn't correct
19 Halted 0 ms 0 KB -