Submission #499288

#	Time	Username	Problem	Language	Result	Execution time	Memory
499288		blue	City Mapping (NOI18_citymapping)	C++17	32 / 100	2 ms	464 KiB

citymapping

#include "citymapping.h"
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

using ll = long long;
using vi = vector<int>;

void find_roads(int N, int Q, int A[], int B[], int W[])
{
	vector< pair<ll, int> > E;
    for(int i = 2; i <= N; i++) E.push_back({get_distance(1, i), i});
    sort(E.begin(), E.end());

    int D = E.back().second;

    E.clear();
    for(int i = 1; i <= N; i++)
        if(i != D)
            E.push_back({get_distance(D, i), i});
    E.push_back({0, D});
    
    sort(E.begin(), E.end());

    for(int i = 0; i < N-1; i++)
    {
        A[i] = E[i].second;
        B[i] = E[i+1].second;
        W[i] = E[i+1].first - E[i].first;
    }
}

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