Submission #924405

#	Time	Username	Problem	Language	Result	Execution time	Memory
924405		pcc	City Mapping (NOI18_citymapping)	C++14	32 / 100	2 ms	604 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[]) {
	vector<pll> coords;
	coords.push_back(make_pair(0ll,1));
	coords.push_back(make_pair(get_distance(1,2),2));
	pll pos = make_pair(0,coords.back().fs);
	for(int i = 3;i<=N;i++){
		ll ta = get_distance(1,i),tb = get_distance(2,i);
		if(ta+tb == pos.sc-pos.fs)coords.push_back(make_pair(ta,i));
		else if(ta<tb)coords.push_back(make_pair(-ta,i));
		else coords.push_back(make_pair(tb+pos.sc,i));
	}
	sort(coords.begin(),coords.end());
	for(int i = 1;i<N;i++){
		A[i-1] = coords[i-1].sc;
		B[i-1] = coords[i].sc;
		W[i-1] = coords[i].fs-coords[i-1].fs;
	}
	return;
}

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