Submission #924102

#	Time	Username	Problem	Language	Result	Execution time	Memory
924102		pcc	City Mapping (NOI18_citymapping)	C++14	25 / 100	97 ms	10944 KiB

citymapping

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

using namespace std;

#define pll pair<ll,ll>
#define fs first
#define sc second
#define ll long long
#define pii pair<int,int>
const int mxn = 1010;
vector<pair<ll,pii>> edges;
int dsu[mxn];

int root(int k){
	return k == dsu[k]?k:dsu[k] = root(dsu[k]);
}

void find_roads(int N, int Q, int A[], int B[], int W[]) {
	for(int i = 1;i<=N;i++){
		for(int j = i+1;j<=N;j++){
			edges.push_back(make_pair(get_distance(i,j),make_pair(i,j)));
		}
	}
	for(int i = 1;i<=N;i++)dsu[i] = i;
	sort(edges.begin(),edges.end());
	int pt = 0;
	for(auto &i:edges){
		int a = i.sc.fs,b = i.sc.sc;
		if(root(a) == root(b))continue;
		A[pt] = a,B[pt] = b,W[pt] = i.fs;
		dsu[root(a)] = root(b);
		pt++;
	}
	return;
}

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