Submission #1253755

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253755		Jer	City Mapping (NOI18_citymapping)	C++20	Running #2-10	183 ms	27856 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

vector<ll> p;
vector<ll> sz;

ll find(ll x) {
    while (x != p[x]) x = p[x];
    return x;
}

void unite(ll a, ll b) {
    a = find(a);
    b = find(b);
    if (sz[a] < sz[b]) swap(a, b);
    p[b] = a;
    sz[a] += sz[b];
}

void find_roads(int n, int Q, int A[], int B[], int W[]) {
    ll cnt = 0;
    p.resize(n);
    sz.assign(n, 1);
    for (int i = 0; i < n; ++i) {
        p[i] = i;
    }
    
    vector<vector<ll>> lst;
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            ll d = get_distance(i, j);
            lst.pb({d, i, j});
        }
    }
    
    sort(lst.begin(), lst.end());
//    for(auto &elt : lst){
//        cout << elt[0] << ' ' << elt[1] << ' ' << elt[2] << endl;
//    }
    
    for (auto &elt: lst) {
        ll a = elt[1] - 1, b = elt[2] - 1, w = elt[0];
        if (find(a) != find(b)) {
            unite(a, b);
            A[cnt] = a + 1;
            B[cnt] = b + 1;
            W[cnt] = w;
            cnt++;
//            cout << a + 1 << ' ' << b + 1 << ' ' << w << endl;
        }
    }
}

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16