Submission #1166941

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166941		zh_h	City Mapping (NOI18_citymapping)	C++20	32 / 100	1 ms	584 KiB

citymapping

#include <bits/stdc++.h>
#include "citymapping.h"
#define pb push_back
using namespace std;

void find_roads(int N, int Q, int A[], int B[], int W[]) {
    // get N, Q
    
    // pick a lucky number: 1
    // find the difference of 1 and all other nodes
    vector<pair<long long, int>> dis1; // {distance, node}
    for (int i = 2; i <= N; i ++) {
        dis1.pb({get_distance(1, i), i});
    }
    sort(dis1.begin(), dis1.end());

    // get longest distance node
    int longest_dis_node = dis1[N-2].second;

    vector<pair<long long, int>> dis2;
    for (int i = 1; i <= N; i ++) {
        if (i == longest_dis_node) {continue;}
        dis2.pb({get_distance(longest_dis_node, i), i});
    }
    sort(dis2.begin(), dis2.end());

    int cur = 0, pre_node = longest_dis_node;
    for (int i = 0; i < N-1; i ++) {
        A[i] = pre_node;
        B[i] = dis2[i].second;
        W[i] = dis2[i].first-cur;
        
        pre_node = dis2[i].second;
        cur = dis2[i].first;
    }

}

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