Submission #1196114

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

citymapping

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

using namespace std;
#define ll long long
#define endl '\n'
#define fi first
#define se second
#define pb push_back

void find_roads(int n, int Q, int A[], int B[], int W[]) {
    ll cnt = 1;
    vector<pair<ll,ll>> arr;
    for (int i = 2; i <= n; ++i) {
        ll d = get_distance(1, i);
        arr.pb({d, i});
    }
    
    sort(arr.begin(), arr.end());
    
    A[0]=1;
    B[0]=arr[0].se;
    W[0]=arr[0].fi;
    ll ptr1=1,ptr2=arr[0].se;
    for (int i = 1; i < n-1; ++i) {
        ll x=arr[i].se;
        ll d1= get_distance(ptr1,x);
        ll d2= get_distance(ptr2,x);
        if (d1<d2){
            A[cnt]=ptr1;
            B[cnt]=x;
            W[cnt]=d1;
            ptr1=x;
            cnt++;
        }
        else{
            A[cnt]=ptr2;
            B[cnt]=x;
            W[cnt]=d2;
            ptr2=x;
            cnt++;
        }
    }
//    for (int i = 0; i < n - 1; ++i) {
//        cout << A[i] << ' ' << B[i] << ' ' << W[i] << endl;
//    }
}

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