Submission #499287

#	Time	Username	Problem	Language	Result	Execution time	Memory
499287		blue	City Mapping (NOI18_citymapping)	C++17	25 / 100	85 ms	8812 KiB

citymapping

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

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

struct edge
{
    ll w;
    int u;
    int v;
};

bool operator < (edge A, edge B)
{
    return A.w < B.w;
}

void find_roads(int N, int Q, int A[], int B[], int W[])
{
	vector<edge> E;
    for(int i = 1; i <= N; i++)
        for(int j = i+1; j <= N; j++)
            E.push_back(edge{get_distance(i, j), i, j});

    sort(E.begin(), E.end());

    int ct = -1;

    vi cc(N+1);
    for(int i = 1; i <= N; i++) cc[i] = i;

    // for(auto e: E) cerr << get<1>(e) << ' ' << get<2>(e) << ' ' << get<0>(e) << '\n';

    for(auto e: E)
    {
        ll w = e.w;
        int u = e.u;
        int v = e.v;
        if(cc[u] == cc[v]) continue;

        int ccu = cc[u];

        for(int i = 1; i <= N; i++)
            if(cc[i] == ccu)
                cc[i] = cc[v];

        ct++;
        A[ct] = u;
        B[ct] = v;
        W[ct] = w;
    }
}

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