oj.uz

Submission #785038

# Submission time Handle Problem Language Result Execution time Memory
785038 2023-07-17T00:43:08 Z Charizard2021 City Mapping (NOI18_citymapping) C++17
100 / 100
 16 ms 8404 KB 
#include<bits/stdc++.h>
#include "citymapping.h"
using namespace std;
const int N = 1000;
long long distances[N][N];
long long get_dst(int x, int y) {
	if (x > y) {
		swap(x, y);
	}
	auto &ret = distances[x][y];
	if (~ret){
		return ret;
	}
	return ret = get_distance(x + 1, y + 1);
}
long long &dist(int x, int y) {
	if (x > y) {
		swap(x, y);
	}
	return distances[x][y];
}
int sizeSubtree[N];
int counter;
vector<pair<int, int> > children[N];
bool visited[N];
vector<pair<int, int> > heavy;
void dfs(int u, int p) {
	sizeSubtree[u] = 1;
	counter++;
	for (pair<int, int> x : children[u]){
        int v = x.first;
		if (!visited[v]) {
			dist(p, v) = dist(p, u) + x.second;
			dfs(v, p);
			sizeSubtree[u] += sizeSubtree[v];
		}
	}
}
int dfs2(int u) {
	pair<int, int> maxVal = {-1, -1};
	for (pair<int, int> x : children[u]){
        int v = x.first;
		if (!visited[v] && (maxVal.first == -1 || sizeSubtree[maxVal.first] < sizeSubtree[v])) {
			maxVal = x;
		}
	}
	if (~maxVal.first) {
		heavy.push_back(maxVal);
		return dfs2(maxVal.first);
	}
	return u;
}
void find_roads(int n, int q, int a[], int b[], int w[]) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			distances[i][j] = -1;
		}
	}
	for (int i = 0; i < n; i++) {
		dist(i, i) = 0;
	}
	vector<pair<long long, int>> ds;
	for (int i = 1; i < n; i++) {
		ds.push_back({get_dst(0, i), i});
	}
	sort(ds.begin(), ds.end());
	int m = 0;
	for (auto &x: ds) {
		int r = 0;
		while (true) {
			counter = 0;
			dfs(r, r);
			if (counter == 1) {
				break;
			}
			int l = dfs2(r);
			long long xl = get_dst(x.second, l), rm = (get_dst(r, x.second) + get_dst(r, l) - xl) / 2;
			for (auto &y: heavy) {
				visited[y.first] = 1;
			}
			int i = 0;
			while (rm > 0) {
				rm -= heavy[i++].second;
			}
			int M = (i ? heavy[i - 1].first: r);
		    dist(M, x.second) = (get_dst(r, x.second) + get_dst(l, x.second) - get_dst(r, l)) / 2;
			heavy.clear();
			r = M;
		}
		a[m] = 1 + r;
        b[m] = 1 + x.second;
        w[m] = dist(r, x.second);
		children[r].push_back({b[m] - 1, w[m]});
		dist(r, b[m] - 1) = w[m];
		m++;
		for (int i = 0; i < n; i++) {
			visited[i] = 0;
		}
	}

}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8276 KB Correct: 2691 out of 500000 queries used.
2 Correct 9 ms 8276 KB Correct: 2421 out of 500000 queries used.
3 Correct 9 ms 8296 KB Correct: 4517 out of 500000 queries used.
4 Correct 9 ms 8276 KB Correct: 5567 out of 500000 queries used.
5 Correct 12 ms 8324 KB Correct: 3387 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8276 KB Correct: 2691 out of 500000 queries used.
2 Correct 9 ms 8276 KB Correct: 2421 out of 500000 queries used.
3 Correct 9 ms 8296 KB Correct: 4517 out of 500000 queries used.
4 Correct 9 ms 8276 KB Correct: 5567 out of 500000 queries used.
5 Correct 12 ms 8324 KB Correct: 3387 out of 500000 queries used.
6 Correct 15 ms 8404 KB Correct: 2009 out of 500000 queries used.
7 Correct 11 ms 8276 KB Correct: 2063 out of 500000 queries used.
8 Correct 9 ms 8276 KB Correct: 4244 out of 500000 queries used.
9 Correct 9 ms 8320 KB Correct: 5089 out of 500000 queries used.
10 Correct 10 ms 8320 KB Correct: 3054 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8352 KB Correct: 2086 out of 12000 queries used.
2 Correct 12 ms 8276 KB Correct: 2304 out of 12000 queries used.
3 Correct 13 ms 8368 KB Correct: 2457 out of 12000 queries used.
4 Correct 13 ms 8324 KB Correct: 2470 out of 12000 queries used.
5 Correct 13 ms 8276 KB Correct: 2240 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8352 KB Correct: 2086 out of 12000 queries used.
2 Correct 12 ms 8276 KB Correct: 2304 out of 12000 queries used.
3 Correct 13 ms 8368 KB Correct: 2457 out of 12000 queries used.
4 Correct 13 ms 8324 KB Correct: 2470 out of 12000 queries used.
5 Correct 13 ms 8276 KB Correct: 2240 out of 12000 queries used.
6 Correct 14 ms 8368 KB Correct: 2473 out of 12000 queries used.
7 Correct 13 ms 8276 KB Correct: 2382 out of 12000 queries used.
8 Correct 13 ms 8404 KB Correct: 2207 out of 12000 queries used.
9 Correct 12 ms 8404 KB Correct: 2235 out of 12000 queries used.
10 Correct 13 ms 8276 KB Correct: 2302 out of 12000 queries used.

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8276 KB Correct: 2691 out of 500000 queries used.
2 Correct 9 ms 8276 KB Correct: 2421 out of 500000 queries used.
3 Correct 9 ms 8296 KB Correct: 4517 out of 500000 queries used.
4 Correct 9 ms 8276 KB Correct: 5567 out of 500000 queries used.
5 Correct 12 ms 8324 KB Correct: 3387 out of 500000 queries used.
6 Correct 15 ms 8404 KB Correct: 2009 out of 500000 queries used.
7 Correct 11 ms 8276 KB Correct: 2063 out of 500000 queries used.
8 Correct 9 ms 8276 KB Correct: 4244 out of 500000 queries used.
9 Correct 9 ms 8320 KB Correct: 5089 out of 500000 queries used.
10 Correct 10 ms 8320 KB Correct: 3054 out of 500000 queries used.
11 Correct 12 ms 8352 KB Correct: 2086 out of 12000 queries used.
12 Correct 12 ms 8276 KB Correct: 2304 out of 12000 queries used.
13 Correct 13 ms 8368 KB Correct: 2457 out of 12000 queries used.
14 Correct 13 ms 8324 KB Correct: 2470 out of 12000 queries used.
15 Correct 13 ms 8276 KB Correct: 2240 out of 12000 queries used.
16 Correct 14 ms 8368 KB Correct: 2473 out of 12000 queries used.
17 Correct 13 ms 8276 KB Correct: 2382 out of 12000 queries used.
18 Correct 13 ms 8404 KB Correct: 2207 out of 12000 queries used.
19 Correct 12 ms 8404 KB Correct: 2235 out of 12000 queries used.
20 Correct 13 ms 8276 KB Correct: 2302 out of 12000 queries used.
21 Correct 16 ms 8276 KB Correct: 2502 out of 25000 queries used.
22 Correct 11 ms 8276 KB Correct: 2071 out of 25000 queries used.
23 Correct 12 ms 8304 KB Correct: 2284 out of 25000 queries used.
24 Correct 12 ms 8276 KB Correct: 2036 out of 25000 queries used.
25 Correct 10 ms 8304 KB Correct: 4436 out of 25000 queries used.
26 Correct 9 ms 8280 KB Correct: 4358 out of 25000 queries used.
27 Correct 9 ms 8308 KB Correct: 4307 out of 25000 queries used.
28 Correct 9 ms 8320 KB Correct: 4417 out of 25000 queries used.
29 Correct 9 ms 8304 KB Correct: 4502 out of 25000 queries used.
30 Correct 9 ms 8288 KB Correct: 4442 out of 25000 queries used.
31 Correct 9 ms 8352 KB Correct: 5151 out of 25000 queries used.
32 Correct 13 ms 8304 KB Correct: 2223 out of 25000 queries used.
33 Correct 9 ms 8304 KB Correct: 5083 out of 25000 queries used.
34 Correct 9 ms 8308 KB Correct: 5158 out of 25000 queries used.
35 Correct 9 ms 8320 KB Correct: 5100 out of 25000 queries used.
36 Correct 9 ms 8216 KB Correct: 5118 out of 25000 queries used.
37 Correct 9 ms 8276 KB Correct: 5144 out of 25000 queries used.
38 Correct 9 ms 8276 KB Correct: 5102 out of 25000 queries used.
39 Correct 9 ms 8304 KB Correct: 5135 out of 25000 queries used.
40 Correct 9 ms 8276 KB Correct: 5168 out of 25000 queries used.
41 Correct 9 ms 8276 KB Correct: 5124 out of 25000 queries used.
42 Correct 9 ms 8276 KB Correct: 5203 out of 25000 queries used.
43 Correct 13 ms 8396 KB Correct: 2087 out of 25000 queries used.
44 Correct 10 ms 8280 KB Correct: 5116 out of 25000 queries used.
45 Correct 8 ms 8188 KB Correct: 5090 out of 25000 queries used.
46 Correct 9 ms 8284 KB Correct: 5068 out of 25000 queries used.
47 Correct 9 ms 8304 KB Correct: 5179 out of 25000 queries used.
48 Correct 9 ms 8276 KB Correct: 5135 out of 25000 queries used.
49 Correct 9 ms 8312 KB Correct: 5091 out of 25000 queries used.
50 Correct 9 ms 8276 KB Correct: 5105 out of 25000 queries used.
51 Correct 11 ms 8276 KB Correct: 5099 out of 25000 queries used.
52 Correct 9 ms 8276 KB Correct: 5128 out of 25000 queries used.
53 Correct 9 ms 8304 KB Correct: 5144 out of 25000 queries used.
54 Correct 11 ms 8308 KB Correct: 2333 out of 25000 queries used.
55 Correct 9 ms 8276 KB Correct: 5196 out of 25000 queries used.
56 Correct 9 ms 8276 KB Correct: 5141 out of 25000 queries used.
57 Correct 9 ms 8276 KB Correct: 5125 out of 25000 queries used.
58 Correct 9 ms 8284 KB Correct: 5115 out of 25000 queries used.
59 Correct 9 ms 8180 KB Correct: 5104 out of 25000 queries used.
60 Correct 10 ms 8276 KB Correct: 3041 out of 25000 queries used.
61 Correct 11 ms 8276 KB Correct: 3317 out of 25000 queries used.
62 Correct 10 ms 8292 KB Correct: 2917 out of 25000 queries used.
63 Correct 11 ms 8356 KB Correct: 3317 out of 25000 queries used.
64 Correct 10 ms 8312 KB Correct: 3103 out of 25000 queries used.
65 Correct 12 ms 8312 KB Correct: 2067 out of 25000 queries used.
66 Correct 11 ms 8308 KB Correct: 3228 out of 25000 queries used.
67 Correct 11 ms 8316 KB Correct: 2018 out of 25000 queries used.
68 Correct 12 ms 8292 KB Correct: 2394 out of 25000 queries used.
69 Correct 12 ms 8276 KB Correct: 2451 out of 25000 queries used.
70 Correct 13 ms 8276 KB Correct: 2414 out of 25000 queries used.