oj.uz

Submission #580741

# Submission time Handle Problem Language Result Execution time Memory
580741 2022-06-21T17:53:27 Z ntabc05101 City Mapping (NOI18_citymapping) C++14
100 / 100
 19 ms 8416 KB 
#include<bits/stdc++.h>
#include "citymapping.h"

using namespace std;

const int mxN = 1000;

long long dst[mxN][mxN];

long long get_dst(int x, int y) {
	if (x > y) {
		swap(x, y);
	}
	auto &ret = dst[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 dst[x][y];
}

int sz[mxN], Cnt;
vector<pair<int, int>> chd[mxN];
bool used[mxN];

void dfs0(int u, int r) {
	sz[u] = 1;
	Cnt++;
	for (auto &to: chd[u]) {
		if (!used[to.first]) {
			dist(r, to.first) = dist(r, u) + to.second;
			dfs0(to.first, r);
			sz[u] += sz[to.first];
		}
	}
}

vector<pair<int, int>> lst;

int dfs1(int u) {
	pair<int, int> mx = {-1, -1};
	for (auto &to: chd[u]) {
		if (!used[to.first] && (mx.first == -1 || sz[mx.first] < sz[to.first])) {
			mx = to;
		}
	}
	if (~mx.first) {
		lst.push_back(mx);
		return dfs1(mx.first);
	}
	return u;
}

void find_roads(int n, int q, int a[], int b[], int w[]) {
	/*a[0] = 2; a[1] = 4; a[2] = 4; a[3] = 5;
	b[0] = 4; b[1] = 1; b[2] = 2; b[3] = 3;
	w[0] = 7; w[1] = 8; w[2] = 1; w[3] = 3;
	return ;*/

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			dst[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});
		//cerr << ds.back().first << " " << ds.back().second << "\n";
	}

	sort(ds.begin(), ds.end());
	int m = 0;
	for (auto &x: ds) {
		int r = 0;
			/*for (int i = 0; i < n; i++) {
				cerr << dist(r, i) << "\n";
			}*/
	
		while (true) {
			Cnt = 0;
			dfs0(r, r);
			if (Cnt == 1) {
				break;
			}
			int l = dfs1(r);
			long long xl = get_dst(x.second, l), rm = (get_dst(r, x.second) + get_dst(r, l) - xl) / 2;
			for (auto &y: lst) {
				used[y.first] = 1;
			}
			int i = 0;
			// cerr << r << " " << get_dst(r, x.second) << " " << get_dst(r, l) << " " << xl << " " << rm;
			while (rm > 0) {
				rm -= lst[i++].second;
			}
			int M = (i ? lst[i - 1].first: r);
			// cerr << " " << l << " " << x.second << " " << M << "\n";
		dist(M, x.second) = (get_dst(r, x.second) + get_dst(l, x.second) - get_dst(r, l)) / 2;
			lst.clear();
			r = M;
		}
		a[m] = 1 + r; b[m] = 1 + x.second; w[m] = dist(r, x.second);
		// cerr << " " << a[m] << " " << b[m] << " " << w[m] << "\n";
		chd[r].push_back({b[m] - 1, w[m]});
		dist(r, b[m] - 1) = w[m];
		m++;
		for (int i = 0; i < n; i++) {
			used[i] = 0;
		}
	}

}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 8276 KB Correct: 2691 out of 500000 queries used.
2 Correct 15 ms 8276 KB Correct: 2421 out of 500000 queries used.
3 Correct 15 ms 8276 KB Correct: 4517 out of 500000 queries used.
4 Correct 13 ms 8276 KB Correct: 5567 out of 500000 queries used.
5 Correct 15 ms 8276 KB Correct: 3387 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 8276 KB Correct: 2691 out of 500000 queries used.
2 Correct 15 ms 8276 KB Correct: 2421 out of 500000 queries used.
3 Correct 15 ms 8276 KB Correct: 4517 out of 500000 queries used.
4 Correct 13 ms 8276 KB Correct: 5567 out of 500000 queries used.
5 Correct 15 ms 8276 KB Correct: 3387 out of 500000 queries used.
6 Correct 17 ms 8308 KB Correct: 2009 out of 500000 queries used.
7 Correct 15 ms 8368 KB Correct: 2063 out of 500000 queries used.
8 Correct 14 ms 8344 KB Correct: 4244 out of 500000 queries used.
9 Correct 14 ms 8320 KB Correct: 5089 out of 500000 queries used.
10 Correct 13 ms 8240 KB Correct: 3054 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 8308 KB Correct: 2086 out of 12000 queries used.
2 Correct 17 ms 8336 KB Correct: 2304 out of 12000 queries used.
3 Correct 18 ms 8380 KB Correct: 2457 out of 12000 queries used.
4 Correct 19 ms 8308 KB Correct: 2470 out of 12000 queries used.
5 Correct 15 ms 8276 KB Correct: 2240 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 8308 KB Correct: 2086 out of 12000 queries used.
2 Correct 17 ms 8336 KB Correct: 2304 out of 12000 queries used.
3 Correct 18 ms 8380 KB Correct: 2457 out of 12000 queries used.
4 Correct 19 ms 8308 KB Correct: 2470 out of 12000 queries used.
5 Correct 15 ms 8276 KB Correct: 2240 out of 12000 queries used.
6 Correct 18 ms 8296 KB Correct: 2473 out of 12000 queries used.
7 Correct 17 ms 8364 KB Correct: 2382 out of 12000 queries used.
8 Correct 16 ms 8308 KB Correct: 2207 out of 12000 queries used.
9 Correct 17 ms 8392 KB Correct: 2235 out of 12000 queries used.
10 Correct 18 ms 8276 KB Correct: 2302 out of 12000 queries used.

Subtask #5
43.0 / 43.0

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