oj.uz

Submission #108518

# Submission time Handle Problem Language Result Execution time Memory
108518 2019-04-30T06:37:26 Z E869120 Amusement Park (JOI17_amusement_park) C++14
82 / 100
 1083 ms 4348 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 = 159;
	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 = 159;
	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 1392 KB Output is correct
2 Correct 47 ms 1152 KB Output is correct
3 Correct 50 ms 1388 KB Output is correct
4 Correct 55 ms 1152 KB Output is correct
5 Correct 47 ms 1288 KB Output is correct
6 Correct 45 ms 1152 KB Output is correct
7 Correct 47 ms 1412 KB Output is correct
8 Correct 48 ms 1396 KB Output is correct
9 Correct 52 ms 1276 KB Output is correct
10 Correct 46 ms 1140 KB Output is correct
11 Correct 74 ms 1584 KB Output is correct
12 Correct 53 ms 1388 KB Output is correct
13 Correct 52 ms 1292 KB Output is correct
14 Correct 50 ms 1292 KB Output is correct
15 Correct 57 ms 1396 KB Output is correct
16 Correct 50 ms 1292 KB Output is correct
17 Correct 51 ms 1392 KB Output is correct
18 Correct 50 ms 1292 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 998 ms 4288 KB Output is correct
2 Correct 938 ms 4348 KB Output is correct
3 Correct 960 ms 4300 KB Output is correct
4 Correct 730 ms 3084 KB Output is correct
5 Correct 962 ms 3120 KB Output is correct
6 Correct 818 ms 3012 KB Output is correct
7 Correct 884 ms 3104 KB Output is correct
8 Correct 848 ms 3228 KB Output is correct
9 Correct 756 ms 3120 KB Output is correct
10 Correct 388 ms 2992 KB Output is correct
11 Correct 376 ms 3148 KB Output is correct
12 Correct 485 ms 2740 KB Output is correct
13 Correct 446 ms 2832 KB Output is correct
14 Correct 463 ms 2864 KB Output is correct
15 Correct 653 ms 2912 KB Output is correct
16 Correct 676 ms 3056 KB Output is correct
17 Correct 686 ms 2940 KB Output is correct
18 Correct 741 ms 2908 KB Output is correct
19 Correct 725 ms 3012 KB Output is correct
20 Correct 457 ms 3256 KB Output is correct
21 Correct 500 ms 3280 KB Output is correct
22 Correct 552 ms 3052 KB Output is correct
23 Correct 517 ms 3008 KB Output is correct
24 Correct 592 ms 3068 KB Output is correct
25 Correct 527 ms 3000 KB Output is correct
26 Correct 569 ms 3120 KB Output is correct
27 Correct 631 ms 2992 KB Output is correct
28 Correct 587 ms 3264 KB Output is correct
29 Correct 511 ms 3104 KB Output is correct
30 Correct 635 ms 2984 KB Output is correct
31 Correct 54 ms 1248 KB Output is correct
32 Correct 45 ms 1152 KB Output is correct
33 Correct 47 ms 1412 KB Output is correct
34 Correct 44 ms 1152 KB Output is correct
35 Correct 50 ms 1288 KB Output is correct
36 Correct 81 ms 1244 KB Output is correct
37 Correct 60 ms 1288 KB Output is correct
38 Correct 54 ms 1280 KB Output is correct
39 Correct 46 ms 1152 KB Output is correct
40 Correct 47 ms 1268 KB Output is correct
41 Correct 48 ms 1408 KB Output is correct
42 Correct 60 ms 1152 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 1288 KB Output is correct
2 Correct 52 ms 1288 KB Output is correct
3 Correct 49 ms 1152 KB Output is correct
4 Correct 98 ms 1676 KB Output is correct
5 Correct 99 ms 1528 KB Output is correct
6 Correct 93 ms 1552 KB Output is correct
7 Correct 100 ms 1676 KB Output is correct
8 Correct 96 ms 1660 KB Output is correct
9 Correct 528 ms 3244 KB Output is correct
10 Correct 640 ms 3760 KB Output is correct
11 Correct 606 ms 3484 KB Output is correct
12 Correct 45 ms 1152 KB Output is correct
13 Correct 52 ms 1152 KB Output is correct
14 Correct 46 ms 1280 KB Output is correct
15 Correct 50 ms 1272 KB Output is correct

Subtask #4
54.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1031 ms 4268 KB Output is correct
2 Correct 990 ms 4164 KB Output is correct
3 Correct 1064 ms 4164 KB Output is correct
4 Correct 722 ms 3000 KB Output is correct
5 Correct 945 ms 3300 KB Output is correct
6 Correct 849 ms 3264 KB Output is correct
7 Correct 769 ms 3168 KB Output is correct
8 Correct 803 ms 3112 KB Output is correct
9 Correct 791 ms 3028 KB Output is correct
10 Correct 429 ms 3220 KB Output is correct
11 Correct 487 ms 3000 KB Output is correct
12 Correct 523 ms 2860 KB Output is correct
13 Partially correct 438 ms 2728 KB Partially correct
14 Correct 481 ms 2856 KB Output is correct
15 Correct 644 ms 2864 KB Output is correct
16 Correct 663 ms 3008 KB Output is correct
17 Correct 669 ms 3000 KB Output is correct
18 Correct 688 ms 2952 KB Output is correct
19 Correct 752 ms 2936 KB Output is correct
20 Correct 475 ms 3432 KB Output is correct
21 Correct 502 ms 3252 KB Output is correct
22 Correct 559 ms 2984 KB Output is correct
23 Correct 583 ms 3000 KB Output is correct
24 Correct 596 ms 3076 KB Output is correct
25 Correct 568 ms 3216 KB Output is correct
26 Correct 597 ms 3272 KB Output is correct
27 Correct 682 ms 3188 KB Output is correct
28 Correct 608 ms 3040 KB Output is correct
29 Correct 527 ms 2948 KB Output is correct
30 Correct 619 ms 3080 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1074 ms 4128 KB Output is correct
2 Correct 1083 ms 4048 KB Output is correct
3 Correct 1006 ms 4132 KB Output is correct
4 Correct 721 ms 2864 KB Output is correct
5 Correct 991 ms 3376 KB Output is correct
6 Correct 831 ms 3068 KB Output is correct
7 Correct 829 ms 3008 KB Output is correct
8 Correct 838 ms 3120 KB Output is correct
9 Correct 828 ms 3192 KB Output is correct
10 Correct 460 ms 3056 KB Output is correct
11 Correct 404 ms 2872 KB Output is correct
12 Correct 530 ms 2808 KB Output is correct
13 Correct 480 ms 2916 KB Output is correct
14 Correct 456 ms 3000 KB Output is correct
15 Correct 731 ms 2896 KB Output is correct
16 Correct 674 ms 2988 KB Output is correct
17 Correct 775 ms 2900 KB Output is correct
18 Correct 745 ms 2992 KB Output is correct
19 Correct 695 ms 2992 KB Output is correct
20 Correct 493 ms 3448 KB Output is correct
21 Correct 469 ms 3372 KB Output is correct
22 Correct 578 ms 3384 KB Output is correct
23 Correct 561 ms 3412 KB Output is correct
24 Correct 547 ms 3268 KB Output is correct
25 Correct 628 ms 3368 KB Output is correct
26 Correct 650 ms 3280 KB Output is correct
27 Correct 597 ms 3468 KB Output is correct
28 Correct 595 ms 3436 KB Output is correct
29 Correct 597 ms 3192 KB Output is correct
30 Correct 655 ms 3204 KB Output is correct
31 Incorrect 52 ms 1252 KB Output isn't correct
32 Halted 0 ms 0 KB -