Submission #321807

#	Time	Username	Problem	Language	Result	Execution time	Memory
321807		wind_reaper	City Mapping (NOI18_citymapping)	C++17	9 / 100	108 ms	16620 KiB

citymapping

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

using namespace std;
struct DSU{
	vector<int> e;
	void init(int n){
		e = vector<int>(n, -1);
	}

	int get(int x){
		return (e[x] < 0 ? x : e[x] = get(e[x]));
	}

	bool same_set(int x, int y){
		return get(x) == get(y);
	}

	bool unite(int x, int y){
		x = get(x), y = get(y);
		if(e[x] < e[y])
			swap(x, y);

		e[x] += e[y];
		e[y] = x;
		return true;
	}
};
void find_roads(int N, int Q, int A[], int B[], int W[]) {
	vector<pair<pair<int, int>, long long>> edges((N*(N-1))/2);
	int c = 0; 
	for(int i = 1; i < N; i++)
		for(int j = i+1; j <= N; j++)
			edges[c++] = {{i, j}, get_distance(i, j)};

	sort(edges.begin(), edges.end(), [&](pair<pair<int, int>, long long> &a, pair<pair<int, int>, long long> &b){
		if(a.second < b.second) return true;
		return false;
	});

	DSU s;
	s.init(N);
	int m = 0;
	vector<int> count(N);
	for(int i = 0; i < c; i++){
		if(s.same_set(edges[i].first.first, edges[i].first.second) || count[edges[i].first.first] >= 3 || count[edges[i].first.second] >= 3) continue;
		s.unite(edges[i].first.first, edges[i].first.second);
		A[m] = edges[i].first.first, B[m] = edges[i].first.second, W[m] = edges[i].second;
		count[A[m]]++, count[B[m]]++;
		m++; 
		if(m == N-1) break;
	}
	return;
}

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