oj.uz

Submission #108532

# Submission time Handle Problem Language Result Execution time Memory
108532 2019-04-30T06:47:05 Z E869120 Amusement Park (JOI17_amusement_park) C++14
82 / 100
 1063 ms 4300 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 = 1640;
	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 = 1640;
	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 43 ms 1152 KB Output is correct
2 Correct 45 ms 1416 KB Output is correct
3 Correct 56 ms 1376 KB Output is correct
4 Correct 46 ms 1280 KB Output is correct
5 Correct 44 ms 1288 KB Output is correct
6 Correct 48 ms 1380 KB Output is correct
7 Correct 52 ms 1280 KB Output is correct
8 Correct 50 ms 1404 KB Output is correct
9 Correct 51 ms 1496 KB Output is correct
10 Correct 47 ms 1288 KB Output is correct
11 Correct 67 ms 1584 KB Output is correct
12 Correct 52 ms 1152 KB Output is correct
13 Correct 47 ms 1392 KB Output is correct
14 Correct 53 ms 1396 KB Output is correct
15 Correct 50 ms 1292 KB Output is correct
16 Correct 53 ms 1276 KB Output is correct
17 Correct 49 ms 1540 KB Output is correct
18 Correct 48 ms 1292 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1041 ms 4136 KB Output is correct
2 Correct 1049 ms 4300 KB Output is correct
3 Correct 1063 ms 4204 KB Output is correct
4 Correct 703 ms 2992 KB Output is correct
5 Correct 959 ms 3248 KB Output is correct
6 Correct 741 ms 3128 KB Output is correct
7 Correct 824 ms 3276 KB Output is correct
8 Correct 833 ms 3256 KB Output is correct
9 Correct 788 ms 2740 KB Output is correct
10 Correct 458 ms 3156 KB Output is correct
11 Correct 444 ms 3136 KB Output is correct
12 Correct 474 ms 2724 KB Output is correct
13 Correct 501 ms 2792 KB Output is correct
14 Correct 523 ms 2812 KB Output is correct
15 Correct 666 ms 3032 KB Output is correct
16 Correct 625 ms 2988 KB Output is correct
17 Correct 629 ms 3004 KB Output is correct
18 Correct 699 ms 2948 KB Output is correct
19 Correct 646 ms 2960 KB Output is correct
20 Correct 428 ms 3132 KB Output is correct
21 Correct 422 ms 3248 KB Output is correct
22 Correct 516 ms 3156 KB Output is correct
23 Correct 616 ms 3240 KB Output is correct
24 Correct 519 ms 2992 KB Output is correct
25 Correct 597 ms 3248 KB Output is correct
26 Correct 599 ms 3124 KB Output is correct
27 Correct 535 ms 3176 KB Output is correct
28 Correct 546 ms 3256 KB Output is correct
29 Correct 466 ms 3024 KB Output is correct
30 Correct 543 ms 3252 KB Output is correct
31 Correct 88 ms 1516 KB Output is correct
32 Correct 47 ms 1424 KB Output is correct
33 Correct 54 ms 1396 KB Output is correct
34 Correct 49 ms 1288 KB Output is correct
35 Correct 45 ms 1144 KB Output is correct
36 Correct 46 ms 1288 KB Output is correct
37 Correct 43 ms 1288 KB Output is correct
38 Correct 49 ms 1148 KB Output is correct
39 Correct 43 ms 1288 KB Output is correct
40 Correct 44 ms 1152 KB Output is correct
41 Correct 43 ms 1144 KB Output is correct
42 Correct 44 ms 1332 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 1376 KB Output is correct
2 Correct 52 ms 1240 KB Output is correct
3 Correct 54 ms 1152 KB Output is correct
4 Correct 96 ms 1680 KB Output is correct
5 Correct 83 ms 1776 KB Output is correct
6 Correct 94 ms 1672 KB Output is correct
7 Correct 88 ms 1676 KB Output is correct
8 Correct 104 ms 1648 KB Output is correct
9 Correct 514 ms 3544 KB Output is correct
10 Correct 610 ms 3540 KB Output is correct
11 Correct 581 ms 3620 KB Output is correct
12 Correct 49 ms 1236 KB Output is correct
13 Correct 50 ms 1332 KB Output is correct
14 Correct 47 ms 1152 KB Output is correct
15 Correct 49 ms 1152 KB Output is correct

Subtask #4
54.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1016 ms 4168 KB Output is correct
2 Correct 1008 ms 4132 KB Output is correct
3 Correct 1041 ms 4176 KB Output is correct
4 Correct 724 ms 2904 KB Output is correct
5 Correct 893 ms 3232 KB Output is correct
6 Correct 879 ms 3248 KB Output is correct
7 Correct 816 ms 3092 KB Output is correct
8 Correct 736 ms 2984 KB Output is correct
9 Correct 817 ms 2928 KB Output is correct
10 Correct 431 ms 2992 KB Output is correct
11 Correct 388 ms 3056 KB Output is correct
12 Correct 425 ms 2668 KB Output is correct
13 Correct 421 ms 2856 KB Output is correct
14 Correct 464 ms 2832 KB Output is correct
15 Correct 596 ms 2992 KB Output is correct
16 Correct 638 ms 2864 KB Output is correct
17 Correct 727 ms 2776 KB Output is correct
18 Correct 722 ms 2968 KB Output is correct
19 Partially correct 687 ms 2904 KB Partially correct
20 Correct 431 ms 3180 KB Output is correct
21 Partially correct 443 ms 3248 KB Partially correct
22 Partially correct 546 ms 3004 KB Partially correct
23 Correct 547 ms 3084 KB Output is correct
24 Correct 603 ms 3068 KB Output is correct
25 Correct 516 ms 3016 KB Output is correct
26 Correct 591 ms 3092 KB Output is correct
27 Correct 645 ms 3152 KB Output is correct
28 Correct 620 ms 2972 KB Output is correct
29 Correct 534 ms 2928 KB Output is correct
30 Correct 535 ms 2976 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1045 ms 4136 KB Output is correct
2 Correct 1020 ms 4144 KB Output is correct
3 Correct 1052 ms 4132 KB Output is correct
4 Correct 737 ms 3028 KB Output is correct
5 Correct 950 ms 3468 KB Output is correct
6 Correct 874 ms 3020 KB Output is correct
7 Correct 758 ms 3056 KB Output is correct
8 Correct 710 ms 3108 KB Output is correct
9 Correct 702 ms 3148 KB Output is correct
10 Correct 380 ms 3032 KB Output is correct
11 Correct 386 ms 3028 KB Output is correct
12 Correct 470 ms 2656 KB Output is correct
13 Correct 488 ms 2640 KB Output is correct
14 Correct 467 ms 2900 KB Output is correct
15 Correct 709 ms 2928 KB Output is correct
16 Correct 623 ms 3040 KB Output is correct
17 Correct 696 ms 2852 KB Output is correct
18 Correct 681 ms 2932 KB Output is correct
19 Correct 687 ms 2940 KB Output is correct
20 Correct 461 ms 3168 KB Output is correct
21 Incorrect 504 ms 3156 KB Output isn't correct
22 Halted 0 ms 0 KB -