oj.uz

답안 #108542

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
108542 2019-04-30T07:00:48 Z E869120 Amusement Park (JOI17_amusement_park) C++14
83 / 100
 1141 ms 4392 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 = 2700;
	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>
#include <ctime>
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 = 2700;
	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) {
	srand((unsigned)time(NULL));
	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, cntv = 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; }
		}
		if (cntv + (E.size() - 1) > 120 && T == 5) {
			if (rand() % 2 == 0) rem += (1LL << id);
		}
		else {
			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];
			cntv += (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:32: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:41: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:87:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 1; j < E.size(); j++) {
                    ~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 1236 KB Output is correct
2 Correct 53 ms 1244 KB Output is correct
3 Correct 55 ms 1396 KB Output is correct
4 Correct 47 ms 1248 KB Output is correct
5 Correct 51 ms 1152 KB Output is correct
6 Correct 61 ms 1236 KB Output is correct
7 Correct 53 ms 1456 KB Output is correct
8 Correct 50 ms 1264 KB Output is correct
9 Correct 55 ms 1296 KB Output is correct
10 Correct 52 ms 1400 KB Output is correct
11 Correct 77 ms 1568 KB Output is correct
12 Correct 48 ms 1288 KB Output is correct
13 Correct 54 ms 1396 KB Output is correct
14 Correct 47 ms 1472 KB Output is correct
15 Correct 54 ms 1524 KB Output is correct
16 Correct 59 ms 1264 KB Output is correct
17 Correct 61 ms 1276 KB Output is correct
18 Correct 59 ms 1276 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1141 ms 4148 KB Output is correct
2 Correct 960 ms 4156 KB Output is correct
3 Correct 1091 ms 4140 KB Output is correct
4 Correct 807 ms 2908 KB Output is correct
5 Correct 922 ms 3156 KB Output is correct
6 Correct 887 ms 2988 KB Output is correct
7 Correct 846 ms 2996 KB Output is correct
8 Correct 901 ms 3164 KB Output is correct
9 Correct 824 ms 3212 KB Output is correct
10 Correct 389 ms 3012 KB Output is correct
11 Correct 391 ms 2912 KB Output is correct
12 Correct 514 ms 2800 KB Output is correct
13 Correct 513 ms 2796 KB Output is correct
14 Correct 537 ms 2748 KB Output is correct
15 Correct 719 ms 2952 KB Output is correct
16 Correct 661 ms 2892 KB Output is correct
17 Correct 764 ms 3000 KB Output is correct
18 Correct 655 ms 2932 KB Output is correct
19 Correct 674 ms 2976 KB Output is correct
20 Correct 445 ms 3256 KB Output is correct
21 Correct 456 ms 3156 KB Output is correct
22 Correct 653 ms 2972 KB Output is correct
23 Correct 606 ms 3176 KB Output is correct
24 Correct 673 ms 3092 KB Output is correct
25 Correct 618 ms 3088 KB Output is correct
26 Correct 615 ms 3228 KB Output is correct
27 Correct 625 ms 3104 KB Output is correct
28 Correct 611 ms 3192 KB Output is correct
29 Correct 493 ms 2976 KB Output is correct
30 Correct 586 ms 3048 KB Output is correct
31 Correct 52 ms 1392 KB Output is correct
32 Correct 52 ms 1408 KB Output is correct
33 Correct 49 ms 1404 KB Output is correct
34 Correct 48 ms 1152 KB Output is correct
35 Correct 53 ms 1152 KB Output is correct
36 Correct 46 ms 1144 KB Output is correct
37 Correct 47 ms 1400 KB Output is correct
38 Correct 48 ms 1288 KB Output is correct
39 Correct 54 ms 1288 KB Output is correct
40 Correct 55 ms 1152 KB Output is correct
41 Correct 51 ms 1152 KB Output is correct
42 Correct 47 ms 1152 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 1152 KB Output is correct
2 Correct 51 ms 1280 KB Output is correct
3 Correct 46 ms 1152 KB Output is correct
4 Correct 100 ms 1692 KB Output is correct
5 Correct 86 ms 1556 KB Output is correct
6 Correct 114 ms 1804 KB Output is correct
7 Correct 112 ms 1560 KB Output is correct
8 Correct 91 ms 1704 KB Output is correct
9 Correct 468 ms 3512 KB Output is correct
10 Correct 575 ms 3640 KB Output is correct
11 Correct 582 ms 3496 KB Output is correct
12 Correct 45 ms 1280 KB Output is correct
13 Correct 46 ms 1288 KB Output is correct
14 Correct 50 ms 1420 KB Output is correct
15 Correct 48 ms 1152 KB Output is correct

Subtask #4
55.0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 993 ms 4212 KB Output is correct
2 Correct 1111 ms 4392 KB Output is correct
3 Correct 1018 ms 4296 KB Output is correct
4 Correct 721 ms 3004 KB Output is correct
5 Correct 912 ms 3400 KB Output is correct
6 Correct 849 ms 3120 KB Output is correct
7 Correct 775 ms 2992 KB Output is correct
8 Correct 820 ms 3188 KB Output is correct
9 Correct 785 ms 3128 KB Output is correct
10 Correct 391 ms 3080 KB Output is correct
11 Correct 408 ms 3176 KB Output is correct
12 Correct 503 ms 2716 KB Output is correct
13 Correct 476 ms 2728 KB Output is correct
14 Correct 465 ms 2856 KB Output is correct
15 Correct 586 ms 2864 KB Output is correct
16 Correct 672 ms 3104 KB Output is correct
17 Correct 761 ms 3136 KB Output is correct
18 Correct 736 ms 3100 KB Output is correct
19 Correct 674 ms 3000 KB Output is correct
20 Correct 457 ms 3224 KB Output is correct
21 Correct 483 ms 3120 KB Output is correct
22 Correct 706 ms 3156 KB Output is correct
23 Correct 568 ms 2996 KB Output is correct
24 Correct 521 ms 3124 KB Output is correct
25 Correct 647 ms 3000 KB Output is correct
26 Correct 605 ms 3248 KB Output is correct
27 Correct 552 ms 3128 KB Output is correct
28 Correct 553 ms 3088 KB Output is correct
29 Correct 525 ms 3112 KB Output is correct
30 Correct 547 ms 3128 KB Output is correct

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1037 ms 4244 KB Output is correct
2 Correct 1111 ms 4072 KB Output is correct
3 Correct 945 ms 4180 KB Output is correct
4 Correct 660 ms 3004 KB Output is correct
5 Correct 872 ms 3492 KB Output is correct
6 Correct 827 ms 3128 KB Output is correct
7 Correct 819 ms 3228 KB Output is correct
8 Correct 785 ms 3176 KB Output is correct
9 Correct 805 ms 3152 KB Output is correct
10 Correct 441 ms 3068 KB Output is correct
11 Correct 460 ms 3056 KB Output is correct
12 Correct 559 ms 2856 KB Output is correct
13 Correct 439 ms 2720 KB Output is correct
14 Correct 502 ms 2940 KB Output is correct
15 Correct 680 ms 3000 KB Output is correct
16 Correct 579 ms 2972 KB Output is correct
17 Correct 722 ms 2912 KB Output is correct
18 Correct 701 ms 2944 KB Output is correct
19 Correct 703 ms 3124 KB Output is correct
20 Correct 457 ms 3644 KB Output is correct
21 Correct 440 ms 3248 KB Output is correct
22 Correct 566 ms 3264 KB Output is correct
23 Correct 557 ms 2992 KB Output is correct
24 Correct 557 ms 3256 KB Output is correct
25 Correct 623 ms 3120 KB Output is correct
26 Correct 578 ms 3000 KB Output is correct
27 Correct 577 ms 3120 KB Output is correct
28 Correct 585 ms 3120 KB Output is correct
29 Correct 529 ms 2984 KB Output is correct
30 Correct 551 ms 3032 KB Output is correct
31 Correct 48 ms 1156 KB Output is correct
32 Correct 63 ms 1288 KB Output is correct
33 Correct 55 ms 1380 KB Output is correct
34 Correct 44 ms 1288 KB Output is correct
35 Correct 44 ms 1288 KB Output is correct
36 Correct 48 ms 1152 KB Output is correct
37 Correct 52 ms 1528 KB Output is correct
38 Correct 50 ms 1388 KB Output is correct
39 Correct 52 ms 1152 KB Output is correct
40 Correct 55 ms 1288 KB Output is correct
41 Incorrect 51 ms 1388 KB Wrong Answer [7]
42 Halted 0 ms 0 KB -