Submission #1167240

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167240		duckindog	City Mapping (NOI18_citymapping)	C++20	25 / 100	175 ms	8876 KiB

citymapping

#include <bits/stdc++.h>

using namespace std;

#include "citymapping.h"

const int MAXN = 1000 + 10;

void find_roads(int N, int Q, int A[], int B[], int W[]) {
	using TP = tuple<long long, int, int>;
	priority_queue<TP, vector<TP>, greater<>> pq;

	set<int> mk{1};
	auto addEdge = [&](int x) { 
		for (int i = 1; i <= N; ++i) { 
			if (mk.count(i)) continue;
			pq.push({get_distance(x, i), x, i});
		}
	};
	addEdge(1);

	int num = 0;
	while (pq.size()) { 
		auto [w, a, b] = pq.top(); pq.pop();
		if (mk.count(b)) continue;
		mk.insert(b);
		
		A[num] = a;
		B[num] = b;
		W[num] = w;
		num += 1;

		addEdge(b);
	}
}

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