oj.uz

Submission #945493

# Submission time Handle Problem Language Result Execution time Memory
945493 2024-03-14T00:40:53 Z vjudge1 City Mapping (NOI18_citymapping) C++14
100 / 100
 16 ms 8796 KB 
#include <bits/stdc++.h>

#include "citymapping.h"
using namespace std;

void find_roads(int N, int Q, int A[], int B[], int W[]) {
    vector<vector<int64_t>> dist(N, vector<int64_t>(N));
    auto ask = [&](int x, int y) {
        if (x == y) return static_cast<int64_t>(0);
        if (dist[x][y]) return dist[x][y];
        return dist[x][y] = dist[y][x] = get_distance(x + 1, y + 1);
    };

    vector<vector<int>> adj(N);

    int counter = 0;
    auto add_edge = [&](int x, int y, int64_t z) {
        A[counter] = x + 1;
        B[counter] = y + 1;
        W[counter++] = z;
        adj[x].emplace_back(y);
    };

    vector<int> weight(N), done(N);

    function<int(int)> dfs = [&](int u) {
        weight[u] = 1;
        for (int v : adj[u]) {
            if (!done[v]) weight[u] += dfs(v);
        }
        return weight[u];
    };

    vector<pair<int64_t, int>> dist_list;
    for (int i = 1; i < N; i++) {
        dist_list.emplace_back(ask(0, i), i);
    }
    sort(dist_list.begin(), dist_list.end());

    for (auto&& [d, j] : dist_list) {
        int root = 0;
        while (dfs(root) > 1) {
            vector<int> path(1, root);
            int leaf = root;
            while (adj[leaf].size()) {
                int _i, best = -1;
                for (int _j : adj[leaf]) {
                    if (done[_j]) continue;
                    if (best < weight[_j]) best = weight[_j], _i = _j;
                }
                if (best == -1) break;
                leaf = _i;
                path.emplace_back(leaf);
            }
            int64_t jr = ask(0, j) - ask(0, root);
            int64_t rl = ask(0, leaf) - ask(0, root);
            int64_t lj = ask(j, leaf);
            int64_t s = jr + rl + lj >> 1;
            int64_t r = s - lj;
            for (int i = 0; i < path.size(); i++) {
                int u = path[i];
                if (ask(0, u) - ask(0, root) == r) {
                    root = u;
                    if (i + 1 < path.size()) done[path[i + 1]] = 1;  // block the larger branch
                    break;
                }
            }
        }
        add_edge(root, j, d - ask(0, root));
        for (int i = 0; i < N; i++) done[i] = 0;
    }
}

Compilation message

citymapping.cpp: In function 'void find_roads(int, int, int*, int*, int*)':
citymapping.cpp:41:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |     for (auto&& [d, j] : dist_list) {
      |                 ^
citymapping.cpp:59:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |             int64_t s = jr + rl + lj >> 1;
      |                         ~~~~~~~~^~~~
citymapping.cpp:61:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |             for (int i = 0; i < path.size(); i++) {
      |                             ~~^~~~~~~~~~~~~
citymapping.cpp:65:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |                     if (i + 1 < path.size()) done[path[i + 1]] = 1;  // block the larger branch
      |                         ~~~~~~^~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8284 KB Correct: 2691 out of 500000 queries used.
2 Correct 11 ms 8536 KB Correct: 2421 out of 500000 queries used.
3 Correct 11 ms 8284 KB Correct: 4517 out of 500000 queries used.
4 Correct 11 ms 8284 KB Correct: 5567 out of 500000 queries used.
5 Correct 13 ms 8484 KB Correct: 3387 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8284 KB Correct: 2691 out of 500000 queries used.
2 Correct 11 ms 8536 KB Correct: 2421 out of 500000 queries used.
3 Correct 11 ms 8284 KB Correct: 4517 out of 500000 queries used.
4 Correct 11 ms 8284 KB Correct: 5567 out of 500000 queries used.
5 Correct 13 ms 8484 KB Correct: 3387 out of 500000 queries used.
6 Correct 15 ms 8284 KB Correct: 2009 out of 500000 queries used.
7 Correct 12 ms 8284 KB Correct: 2063 out of 500000 queries used.
8 Correct 10 ms 8264 KB Correct: 4244 out of 500000 queries used.
9 Correct 11 ms 8284 KB Correct: 5089 out of 500000 queries used.
10 Correct 12 ms 8340 KB Correct: 3054 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8284 KB Correct: 2086 out of 12000 queries used.
2 Correct 15 ms 8420 KB Correct: 2304 out of 12000 queries used.
3 Correct 16 ms 8792 KB Correct: 2457 out of 12000 queries used.
4 Correct 14 ms 8428 KB Correct: 2470 out of 12000 queries used.
5 Correct 14 ms 8400 KB Correct: 2240 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8284 KB Correct: 2086 out of 12000 queries used.
2 Correct 15 ms 8420 KB Correct: 2304 out of 12000 queries used.
3 Correct 16 ms 8792 KB Correct: 2457 out of 12000 queries used.
4 Correct 14 ms 8428 KB Correct: 2470 out of 12000 queries used.
5 Correct 14 ms 8400 KB Correct: 2240 out of 12000 queries used.
6 Correct 15 ms 8280 KB Correct: 2473 out of 12000 queries used.
7 Correct 14 ms 8284 KB Correct: 2382 out of 12000 queries used.
8 Correct 16 ms 8796 KB Correct: 2207 out of 12000 queries used.
9 Correct 14 ms 8540 KB Correct: 2235 out of 12000 queries used.
10 Correct 14 ms 8284 KB Correct: 2302 out of 12000 queries used.

Subtask #5
43.0 / 43.0

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