oj.uz

Submission #784245

# Submission time Handle Problem Language Result Execution time Memory
784245 2023-07-15T21:58:58 Z rainboy City Mapping (NOI18_citymapping) C++17
100 / 100
 8 ms 616 KB 
#include "citymapping.h"
#include <stdio.h>
#include <stdlib.h>

const int N = 1000;

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int *ej[N], eo[N], jj[N], jj_[N]; long long dd[N];

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
		while (j < k)
			if (dd[ii[j]] == dd[i_])
				j++;
			else if (dd[ii[j]] < dd[i_]) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		sort(ii, l, i);
		l = k;
	}
}

void append(int i, int j) {
	int o = eo[i]++;
	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
	ej[i][o] = j;
}

int dfs(int i) {
	int s = 1, k_ = 0, j_ = -1;
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o], k = dfs(j);
		s += k;
		if (k_ < k)
			k_ = k, j_ = j;
	}
	jj[i] = j_;
	jj_[i] = j_ == -1 ? i : jj_[j_];
	return s;
}

void find_roads(int n, int q, int uu[], int vv[], int ww[]) {
	static int ii[N];
	for (int i = 1; i < n; i++)
		dd[i] = get_distance(1, i + 1);
	for (int i = 1; i < n; i++)
		ii[i] = i;
	sort(ii, 1, n);
	for (int i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]), eo[i] = 0;
	for (int h = 1; h < n; h++) {
		int k = ii[h];
		dfs(0);
		int i = 0;
		while (1) {
			if (eo[i] == 0) {
				append(i, k);
				uu[h - 1] = i + 1, vv[h - 1] = k + 1, ww[h - 1] = dd[k] - dd[i];
				break;
			}
			long long d_ = (dd[jj_[i]] + dd[k] - get_distance(jj_[i] + 1, k + 1)) / 2;
			if (i != 0 || dd[i] < d_) {
				while (dd[i] < d_)
					i = jj[i];
				if (eo[i] <= 1) {
					append(i, k);
					uu[h - 1] = i + 1, vv[h - 1] = k + 1, ww[h - 1] = dd[k] - dd[i];
					break;
				}
				i = ej[i][0] ^ ej[i][1] ^ jj[i];
			} else {
				if (eo[i] == 1) {
					append(i, k);
					uu[h - 1] = i + 1, vv[h - 1] = k + 1, ww[h - 1] = dd[k] - dd[i];
					break;
				} else {
					int j = ej[i][0];
					if (j == jj[i])
						j = ej[i][1];
					long long d_ = (dd[jj_[j]] + dd[k] - get_distance(jj_[j] + 1, k + 1)) / 2;
					if (dd[i] < d_) {
						i = j;
						while (dd[i] < d_)
							i = jj[i];
						if (eo[i] <= 1) {
							append(i, k);
							uu[h - 1] = i + 1, vv[h - 1] = k + 1, ww[h - 1] = dd[k] - dd[i];
							break;
						}
						i = ej[i][0] ^ ej[i][1] ^ jj[i];
					} else {
						if (eo[i] == 2) {
							append(i, k);
							uu[h - 1] = i + 1, vv[h - 1] = k + 1, ww[h - 1] = dd[k] - dd[i];
							break;
						} else
							i = ej[i][0] ^ ej[i][1] ^ ej[i][2] ^ jj[i] ^ j;
					}
				}
			}
		}
	}
	for (int i = 0; i < n; i++)
		free(ej[i]);
}

Compilation message

citymapping.cpp: In function 'void append(int, int)':
citymapping.cpp:35:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   35 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 468 KB Correct: 2682 out of 500000 queries used.
2 Correct 5 ms 468 KB Correct: 2153 out of 500000 queries used.
3 Correct 4 ms 472 KB Correct: 4147 out of 500000 queries used.
4 Correct 4 ms 468 KB Correct: 5146 out of 500000 queries used.
5 Correct 8 ms 508 KB Correct: 3347 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 468 KB Correct: 2682 out of 500000 queries used.
2 Correct 5 ms 468 KB Correct: 2153 out of 500000 queries used.
3 Correct 4 ms 472 KB Correct: 4147 out of 500000 queries used.
4 Correct 4 ms 468 KB Correct: 5146 out of 500000 queries used.
5 Correct 8 ms 508 KB Correct: 3347 out of 500000 queries used.
6 Correct 8 ms 524 KB Correct: 2011 out of 500000 queries used.
7 Correct 5 ms 468 KB Correct: 2059 out of 500000 queries used.
8 Correct 4 ms 468 KB Correct: 3944 out of 500000 queries used.
9 Correct 4 ms 468 KB Correct: 4854 out of 500000 queries used.
10 Correct 6 ms 468 KB Correct: 3002 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 468 KB Correct: 2086 out of 12000 queries used.
2 Correct 6 ms 468 KB Correct: 2316 out of 12000 queries used.
3 Correct 7 ms 596 KB Correct: 2470 out of 12000 queries used.
4 Correct 7 ms 468 KB Correct: 2462 out of 12000 queries used.
5 Correct 6 ms 568 KB Correct: 2251 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 468 KB Correct: 2086 out of 12000 queries used.
2 Correct 6 ms 468 KB Correct: 2316 out of 12000 queries used.
3 Correct 7 ms 596 KB Correct: 2470 out of 12000 queries used.
4 Correct 7 ms 468 KB Correct: 2462 out of 12000 queries used.
5 Correct 6 ms 568 KB Correct: 2251 out of 12000 queries used.
6 Correct 6 ms 472 KB Correct: 2474 out of 12000 queries used.
7 Correct 7 ms 468 KB Correct: 2381 out of 12000 queries used.
8 Correct 7 ms 468 KB Correct: 2201 out of 12000 queries used.
9 Correct 7 ms 468 KB Correct: 2236 out of 12000 queries used.
10 Correct 6 ms 468 KB Correct: 2309 out of 12000 queries used.

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 468 KB Correct: 2682 out of 500000 queries used.
2 Correct 5 ms 468 KB Correct: 2153 out of 500000 queries used.
3 Correct 4 ms 472 KB Correct: 4147 out of 500000 queries used.
4 Correct 4 ms 468 KB Correct: 5146 out of 500000 queries used.
5 Correct 8 ms 508 KB Correct: 3347 out of 500000 queries used.
6 Correct 8 ms 524 KB Correct: 2011 out of 500000 queries used.
7 Correct 5 ms 468 KB Correct: 2059 out of 500000 queries used.
8 Correct 4 ms 468 KB Correct: 3944 out of 500000 queries used.
9 Correct 4 ms 468 KB Correct: 4854 out of 500000 queries used.
10 Correct 6 ms 468 KB Correct: 3002 out of 500000 queries used.
11 Correct 7 ms 468 KB Correct: 2086 out of 12000 queries used.
12 Correct 6 ms 468 KB Correct: 2316 out of 12000 queries used.
13 Correct 7 ms 596 KB Correct: 2470 out of 12000 queries used.
14 Correct 7 ms 468 KB Correct: 2462 out of 12000 queries used.
15 Correct 6 ms 568 KB Correct: 2251 out of 12000 queries used.
16 Correct 6 ms 472 KB Correct: 2474 out of 12000 queries used.
17 Correct 7 ms 468 KB Correct: 2381 out of 12000 queries used.
18 Correct 7 ms 468 KB Correct: 2201 out of 12000 queries used.
19 Correct 7 ms 468 KB Correct: 2236 out of 12000 queries used.
20 Correct 6 ms 468 KB Correct: 2309 out of 12000 queries used.
21 Correct 7 ms 596 KB Correct: 2488 out of 25000 queries used.
22 Correct 5 ms 472 KB Correct: 2070 out of 25000 queries used.
23 Correct 5 ms 476 KB Correct: 2289 out of 25000 queries used.
24 Correct 7 ms 468 KB Correct: 2040 out of 25000 queries used.
25 Correct 5 ms 476 KB Correct: 4172 out of 25000 queries used.
26 Correct 4 ms 468 KB Correct: 4034 out of 25000 queries used.
27 Correct 5 ms 468 KB Correct: 3988 out of 25000 queries used.
28 Correct 4 ms 468 KB Correct: 4077 out of 25000 queries used.
29 Correct 4 ms 468 KB Correct: 4183 out of 25000 queries used.
30 Correct 4 ms 472 KB Correct: 4087 out of 25000 queries used.
31 Correct 4 ms 468 KB Correct: 4905 out of 25000 queries used.
32 Correct 6 ms 468 KB Correct: 2221 out of 25000 queries used.
33 Correct 4 ms 468 KB Correct: 4834 out of 25000 queries used.
34 Correct 4 ms 468 KB Correct: 4909 out of 25000 queries used.
35 Correct 6 ms 516 KB Correct: 4847 out of 25000 queries used.
36 Correct 4 ms 468 KB Correct: 4866 out of 25000 queries used.
37 Correct 4 ms 468 KB Correct: 4876 out of 25000 queries used.
38 Correct 4 ms 520 KB Correct: 4841 out of 25000 queries used.
39 Correct 4 ms 524 KB Correct: 4891 out of 25000 queries used.
40 Correct 4 ms 468 KB Correct: 4879 out of 25000 queries used.
41 Correct 6 ms 468 KB Correct: 4871 out of 25000 queries used.
42 Correct 4 ms 472 KB Correct: 4912 out of 25000 queries used.
43 Correct 7 ms 468 KB Correct: 2085 out of 25000 queries used.
44 Correct 4 ms 468 KB Correct: 4857 out of 25000 queries used.
45 Correct 4 ms 468 KB Correct: 4807 out of 25000 queries used.
46 Correct 4 ms 460 KB Correct: 4802 out of 25000 queries used.
47 Correct 5 ms 468 KB Correct: 4883 out of 25000 queries used.
48 Correct 4 ms 468 KB Correct: 4877 out of 25000 queries used.
49 Correct 4 ms 476 KB Correct: 4858 out of 25000 queries used.
50 Correct 4 ms 476 KB Correct: 4852 out of 25000 queries used.
51 Correct 4 ms 468 KB Correct: 4853 out of 25000 queries used.
52 Correct 4 ms 468 KB Correct: 4860 out of 25000 queries used.
53 Correct 4 ms 468 KB Correct: 4912 out of 25000 queries used.
54 Correct 5 ms 468 KB Correct: 2337 out of 25000 queries used.
55 Correct 5 ms 468 KB Correct: 4952 out of 25000 queries used.
56 Correct 4 ms 468 KB Correct: 4885 out of 25000 queries used.
57 Correct 4 ms 468 KB Correct: 4871 out of 25000 queries used.
58 Correct 4 ms 476 KB Correct: 4826 out of 25000 queries used.
59 Correct 4 ms 468 KB Correct: 4873 out of 25000 queries used.
60 Correct 6 ms 468 KB Correct: 2996 out of 25000 queries used.
61 Correct 6 ms 468 KB Correct: 3282 out of 25000 queries used.
62 Correct 6 ms 476 KB Correct: 2869 out of 25000 queries used.
63 Correct 7 ms 616 KB Correct: 3278 out of 25000 queries used.
64 Correct 5 ms 468 KB Correct: 3063 out of 25000 queries used.
65 Correct 6 ms 468 KB Correct: 2063 out of 25000 queries used.
66 Correct 6 ms 468 KB Correct: 3165 out of 25000 queries used.
67 Correct 6 ms 556 KB Correct: 2015 out of 25000 queries used.
68 Correct 5 ms 468 KB Correct: 2398 out of 25000 queries used.
69 Correct 5 ms 468 KB Correct: 2453 out of 25000 queries used.
70 Correct 5 ms 468 KB Correct: 2416 out of 25000 queries used.