Submission #1063892

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063892		Luvidi	City Mapping (NOI18_citymapping)	C++17	25 / 100	90 ms	8904 KiB

citymapping

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

#define ll long long

const int maxn=1e3;
int par[maxn+1];

int rep(int x){
	if(x==par[x])return x;
	return par[x]=rep(par[x]);
}

bool join(int x,int y){
	x=rep(x);
	y=rep(y);
	par[x]=y;
	return x!=y;
}

void find_roads(int n, int q, int a[], int b[], int w[]) {
	vector<pair<ll,pair<int,int>>> edge;
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			ll d=get_distance(i,j);
			edge.push_back({d,{i,j}});
		}
		par[i]=i;
	}
	sort(edge.begin(),edge.end());
	int cnt=0;
	for(auto [d,p]:edge){
		auto[x,y]=p;
		if(join(x,y)){
			a[cnt]=x;
			b[cnt]=y;
			w[cnt]=d;
			cnt++;
		}
	}
}

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