oj.uz

Submission #1024578

# Submission time Handle Problem Language Result Execution time Memory
1024578 2024-07-16T08:14:37 Z thinknoexit City Mapping (NOI18_citymapping) C++17
57 / 100
 4 ms 8796 KB 
#include "citymapping.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1010;
int n;
ll dis[N][N];
int A[N], B[N], W[N], tot;
ll d(int i, int j) {
	if (i == j) return 0;
	if (!dis[i][j]) return dis[i][j] = dis[j][i] = get_distance(i, j);
	return dis[i][j];
}
void play(vector<int>& v) {
	int m = v.size();
	if (m == 1) return;
	ll mx = 0;
	int U, V;
	for (int j = 1;j < m;j++) {
		if (d(v[0], v[j]) > mx) {
			mx = d(v[0], v[j]);
			U = v[j];
		}
	}
	mx = 0;
	for (int j = 0;j < m;j++) {
		if (d(U, v[j]) > mx) {
			mx = d(U, v[j]);
			V = v[j];
		}
	}
	// U, V is leaf
	ll all = d(U, V);
	vector<pair<ll, int>> in, rem;
	for (int j = 0;j < m;j++) {
		if (d(U, v[j]) + d(v[j], V) == all) {
			in.push_back({ d(U, v[j]), v[j] });
		}
		else {
			ll extra = (d(U, v[j]) + d(v[j], V) - all) / 2;
			rem.push_back({ d(U, v[j]) - extra, v[j] });
		}
	}
	sort(in.begin(), in.end());
	sort(rem.begin(), rem.end());
	vector<vector<int>> r;
	int p = 0;
	for (int i = 1;i < (int)in.size();i++) {
		A[tot] = in[i - 1].second;
		B[tot] = in[i].second;
		W[tot] = in[i].first - in[i - 1].first;
		tot++;
		vector<int> nw;
		ll mn = LLONG_MAX;
		int idx = 0;
		while (p < (int)rem.size() && rem[p].first == in[i].first) {
			int vl = rem[p].second;
			ll extra = (d(U, vl) + d(vl, V) - all) / 2;
			if (extra < mn) {
				mn = extra;
				idx = vl;
			}
			nw.push_back(vl);
			p++;
		}
		if (!nw.empty()) {
			A[tot] = idx;
			B[tot] = in[i].second;
			W[tot] = mn;
			tot++;
			r.push_back(nw);
		}
	}
	for (auto& x : r) play(x);
}
void find_roads(int NN, int Q, int A[], int B[], int W[]) {
	n = NN;
	vector<int> init(n);
	iota(init.begin(), init.end(), 1);
	play(init);
	for (int i = 0;i < n - 1;i++) {
		A[i] = ::A[i];
		B[i] = ::B[i];
		W[i] = ::W[i];
		//cout << A[i] << ' ' << B[i] << ' ' << W[i] << '\n';
	}
	return;
}

Compilation message

citymapping.cpp: In function 'void play(std::vector<int>&)':
citymapping.cpp:10:2: warning: 'U' may be used uninitialized in this function [-Wmaybe-uninitialized]
   10 |  if (i == j) return 0;
      |  ^~
citymapping.cpp:18:6: note: 'U' was declared here
   18 |  int U, V;
      |      ^
citymapping.cpp:10:2: warning: 'V' may be used uninitialized in this function [-Wmaybe-uninitialized]
   10 |  if (i == j) return 0;
      |  ^~
citymapping.cpp:18:9: note: 'V' was declared here
   18 |  int U, V;
      |         ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Correct: 2991 out of 500000 queries used.
2 Correct 2 ms 8024 KB Correct: 2994 out of 500000 queries used.
3 Correct 3 ms 8284 KB Correct: 7213 out of 500000 queries used.
4 Correct 2 ms 8028 KB Correct: 7931 out of 500000 queries used.
5 Correct 3 ms 8540 KB Correct: 12704 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Correct: 2991 out of 500000 queries used.
2 Correct 2 ms 8024 KB Correct: 2994 out of 500000 queries used.
3 Correct 3 ms 8284 KB Correct: 7213 out of 500000 queries used.
4 Correct 2 ms 8028 KB Correct: 7931 out of 500000 queries used.
5 Correct 3 ms 8540 KB Correct: 12704 out of 500000 queries used.
6 Correct 2 ms 8028 KB Correct: 2982 out of 500000 queries used.
7 Correct 3 ms 8540 KB Correct: 20467 out of 500000 queries used.
8 Correct 3 ms 8284 KB Correct: 7473 out of 500000 queries used.
9 Correct 3 ms 8284 KB Correct: 8748 out of 500000 queries used.
10 Correct 2 ms 8284 KB Correct: 8178 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB Correct: 2967 out of 12000 queries used.
2 Correct 2 ms 8028 KB Correct: 2973 out of 12000 queries used.
3 Correct 2 ms 8284 KB Correct: 2994 out of 12000 queries used.
4 Correct 2 ms 8028 KB Correct: 2973 out of 12000 queries used.
5 Correct 2 ms 8284 KB Correct: 2967 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB Correct: 2967 out of 12000 queries used.
2 Correct 2 ms 8028 KB Correct: 2973 out of 12000 queries used.
3 Correct 2 ms 8284 KB Correct: 2994 out of 12000 queries used.
4 Correct 2 ms 8028 KB Correct: 2973 out of 12000 queries used.
5 Correct 2 ms 8284 KB Correct: 2967 out of 12000 queries used.
6 Correct 2 ms 8284 KB Correct: 2988 out of 12000 queries used.
7 Correct 2 ms 8024 KB Correct: 2982 out of 12000 queries used.
8 Correct 2 ms 8284 KB Correct: 2994 out of 12000 queries used.
9 Correct 2 ms 8284 KB Correct: 2985 out of 12000 queries used.
10 Correct 2 ms 8284 KB Correct: 2976 out of 12000 queries used.

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Correct: 2991 out of 500000 queries used.
2 Correct 2 ms 8024 KB Correct: 2994 out of 500000 queries used.
3 Correct 3 ms 8284 KB Correct: 7213 out of 500000 queries used.
4 Correct 2 ms 8028 KB Correct: 7931 out of 500000 queries used.
5 Correct 3 ms 8540 KB Correct: 12704 out of 500000 queries used.
6 Correct 2 ms 8028 KB Correct: 2982 out of 500000 queries used.
7 Correct 3 ms 8540 KB Correct: 20467 out of 500000 queries used.
8 Correct 3 ms 8284 KB Correct: 7473 out of 500000 queries used.
9 Correct 3 ms 8284 KB Correct: 8748 out of 500000 queries used.
10 Correct 2 ms 8284 KB Correct: 8178 out of 500000 queries used.
11 Correct 2 ms 8028 KB Correct: 2967 out of 12000 queries used.
12 Correct 2 ms 8028 KB Correct: 2973 out of 12000 queries used.
13 Correct 2 ms 8284 KB Correct: 2994 out of 12000 queries used.
14 Correct 2 ms 8028 KB Correct: 2973 out of 12000 queries used.
15 Correct 2 ms 8284 KB Correct: 2967 out of 12000 queries used.
16 Correct 2 ms 8284 KB Correct: 2988 out of 12000 queries used.
17 Correct 2 ms 8024 KB Correct: 2982 out of 12000 queries used.
18 Correct 2 ms 8284 KB Correct: 2994 out of 12000 queries used.
19 Correct 2 ms 8284 KB Correct: 2985 out of 12000 queries used.
20 Correct 2 ms 8284 KB Correct: 2976 out of 12000 queries used.
21 Correct 2 ms 8284 KB Correct: 2982 out of 25000 queries used.
22 Correct 3 ms 8028 KB Correct: 6243 out of 25000 queries used.
23 Correct 2 ms 8396 KB Correct: 3056 out of 25000 queries used.
24 Correct 3 ms 8280 KB Correct: 4695 out of 25000 queries used.
25 Correct 2 ms 8284 KB Correct: 7288 out of 25000 queries used.
26 Correct 3 ms 8284 KB Correct: 7061 out of 25000 queries used.
27 Correct 3 ms 8284 KB Correct: 7241 out of 25000 queries used.
28 Correct 3 ms 8432 KB Correct: 7648 out of 25000 queries used.
29 Correct 3 ms 8540 KB Correct: 7847 out of 25000 queries used.
30 Correct 3 ms 8284 KB Correct: 8530 out of 25000 queries used.
31 Correct 3 ms 8284 KB Correct: 8327 out of 25000 queries used.
32 Correct 2 ms 8028 KB Correct: 2979 out of 25000 queries used.
33 Correct 2 ms 8512 KB Correct: 8176 out of 25000 queries used.
34 Correct 3 ms 8284 KB Correct: 8179 out of 25000 queries used.
35 Correct 3 ms 8284 KB Correct: 8107 out of 25000 queries used.
36 Correct 2 ms 8284 KB Correct: 8136 out of 25000 queries used.
37 Correct 3 ms 8284 KB Correct: 8328 out of 25000 queries used.
38 Correct 3 ms 8284 KB Correct: 8388 out of 25000 queries used.
39 Correct 2 ms 8540 KB Correct: 8334 out of 25000 queries used.
40 Correct 3 ms 8540 KB Correct: 8411 out of 25000 queries used.
41 Correct 3 ms 8540 KB Correct: 8228 out of 25000 queries used.
42 Correct 3 ms 8280 KB Correct: 8348 out of 25000 queries used.
43 Correct 2 ms 8540 KB Correct: 2988 out of 25000 queries used.
44 Correct 3 ms 8420 KB Correct: 8092 out of 25000 queries used.
45 Correct 3 ms 8284 KB Correct: 8362 out of 25000 queries used.
46 Correct 3 ms 8284 KB Correct: 8369 out of 25000 queries used.
47 Correct 3 ms 8284 KB Correct: 8225 out of 25000 queries used.
48 Correct 3 ms 8280 KB Correct: 8463 out of 25000 queries used.
49 Correct 2 ms 8284 KB Correct: 8449 out of 25000 queries used.
50 Correct 3 ms 8284 KB Correct: 8205 out of 25000 queries used.
51 Correct 3 ms 8280 KB Correct: 8203 out of 25000 queries used.
52 Correct 3 ms 8540 KB Correct: 8221 out of 25000 queries used.
53 Correct 3 ms 8364 KB Correct: 8490 out of 25000 queries used.
54 Correct 4 ms 8796 KB Correct: 22262 out of 25000 queries used.
55 Correct 3 ms 8284 KB Correct: 8396 out of 25000 queries used.
56 Correct 3 ms 8420 KB Correct: 8255 out of 25000 queries used.
57 Correct 3 ms 8284 KB Correct: 8370 out of 25000 queries used.
58 Correct 3 ms 8480 KB Correct: 8190 out of 25000 queries used.
59 Correct 3 ms 8284 KB Correct: 8167 out of 25000 queries used.
60 Correct 3 ms 8540 KB Correct: 9979 out of 25000 queries used.
61 Correct 3 ms 8348 KB Correct: 9033 out of 25000 queries used.
62 Correct 3 ms 8284 KB Correct: 9140 out of 25000 queries used.
63 Correct 3 ms 8540 KB Correct: 9294 out of 25000 queries used.
64 Correct 3 ms 8284 KB Correct: 8922 out of 25000 queries used.
65 Correct 3 ms 8268 KB Correct: 11687 out of 25000 queries used.
66 Correct 2 ms 8448 KB Correct: 8460 out of 25000 queries used.
67 Correct 2 ms 8528 KB Correct: 3346 out of 25000 queries used.
68 Incorrect 4 ms 8540 KB Too many calls to get_distance().
69 Halted 0 ms 0 KB -