Submission #209488

#	Time	Username	Problem	Language	Result	Execution time	Memory
209488		Alexa2001	City Mapping (NOI18_citymapping)	C++17	100 / 100	28 ms	8312 KiB

citymapping

#include "citymapping.h"
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 1005;
typedef long long ll;

int nr = 0, root, n, sz[Nmax], up[Nmax], where[Nmax], last[Nmax], crt_chain;
ll dist[Nmax][Nmax];
vector<int> v[Nmax];

mt19937 mt(time(0));

int get_rand(int x, int y)
{
    return uniform_int_distribution<int> (x, y) (mt);
}

ll get_dist(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, y);
}

void add_edge(int V[], int U[], int cost[], int x, int y)
{
    if(dist[root][x] > dist[root][y]) swap(x, y);

    V[nr] = x;
    U[nr] = y;
    cost[nr] = dist[root][y] - dist[root][x];
    v[x].push_back(y);
    up[y] = x;

    ++nr;
}

int get_lca(int x, int y)
{
    ll D = (get_dist(root, x) + get_dist(root, y) - get_dist(x, y)) / 2;

    while(dist[root][x] != D)
        x = up[x];
    return x;
}

void dfs0(int node)
{
    sz[node] = 1;

    for(auto it : v[node])
    {
        dfs0(it);
        sz[node] += sz[it];
    }

    sort(v[node].begin(), v[node].end(), [](int x, int y) {return sz[x] > sz[y];});
}

void hp(int node)
{
    where[node] = crt_chain;

    if(v[node].empty())
    {
        last[crt_chain] = node;
        return;
    }

    hp(v[node][0]);

    for(int i=1; i<v[node].size(); ++i)
    {
        ++crt_chain;
        hp(v[node][i]);
    }
}

void process(int node, int V[], int U[], int cost[])
{
    dfs0(root);
    crt_chain = 1;
    hp(root);

    int x = last[1];

    while(1)
    {
        int lca = get_lca(x, node);

        if(lca == x)
        {
            add_edge(V, U, cost, x, node);
            return;
        }

        if(lca == root)
        {
            if(v[root].size() == 1)
            {
                add_edge(V, U, cost, root, node);
                return;
            }

            if(v[root].size() == 2)
            {
                if(where[x] == 1)
                {
                    x = last[where[v[root][1]]];
                    continue;
                }
                else
                {
                    add_edge(V, U, cost, root, node);
                    return;
                }
            }

            if(v[root].size() == 3)
            {
                if(where[x] == 1)
                {
                    x = last[where[v[root][1]]];
                    continue;
                }
                else
                {
                    x = last[where[v[root][2]]];
                    continue;
                }
            }
        }

        if(v[lca].size() == 1)
        {
            add_edge(V, U, cost, lca, node);
            return;
        }
        else if(v[lca].size() == 2)
            x = last[where[v[lca][1]]];
    }
}

void find_roads(int N, int Q, int A[], int B[], int W[])
{
    n = N;

    root = get_rand(1, n);
    int i;
    for(i=1; i<=n; ++i) get_dist(root, i);

    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 1);
    sort(ord.begin(), ord.end(), [](int x, int y) {return dist[root][x] < dist[root][y]; });

    for(auto it : ord)
        if(it != root)
            process(it, A, B, W);
}

Compilation message (stderr)

citymapping.cpp: In function 'void hp(int)':
citymapping.cpp:74:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1; i<v[node].size(); ++i)
                  ~^~~~~~~~~~~~~~~

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