Submission #945490

#	Time	Username	Problem	Language	Result	Execution time	Memory
945490		vjudge1	City Mapping (NOI18_citymapping)	C++14	22 / 100	2066 ms	4652 KiB

citymapping

#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<int>> dist(N, vector<int>(N));
    auto ask = [&](int x, int y) {
        if (x == y) return 0;
        if (dist[x][y]) return dist[x][y];
        return dist[x][y] = dist[y][x] = get_distance(x + 1, y + 1);
    };

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

    int counter = 0;
    auto add_edge = [&](int x, int y, int 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<int> cur(1, 0);
    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());
    vector<int64_t> depth(N);

    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 (stderr)

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

• Subtask 1: 9 / 9
• Subtask 2: 0 / 16
• Subtask 3: 13 / 13
• Subtask 4: 0 / 19
• Subtask 5: 0 / 43