제출 #1253756

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1253756		Jer	City Mapping (NOI18_citymapping)	C++20	25 / 100	87 ms	8876 KiB

citymapping

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

using namespace std;

const int MAXN = 1005;
typedef long long ll;

struct unionFind{
	int par[MAXN], size[MAXN];

	unionFind(){
		for (int i = 0; i < MAXN; i++)
			par[i] = i, size[i] = 1;
	}

	int find(int x){ return (x == par[x]) ? x : (par[x] = find(par[x])); }

	bool same(int a, int b) { return find(a) == find(b) ; }

	void unite(int a, int b) {
		a = find(a), b = find(b);
		
		if (size[a] < size[b]) swap(a, b);

		par[b] = a, size[a] += size[b];
	}
};

#define we(i) get<0>(i)
#define u(i) get<1>(i)
#define v(i) get<2>(i)

void find_roads(int n, int q, int a[], int b[], int w[]) {
	vector<tuple<ll, int, int>> k; // w, a, b
	
	unionFind uf;

	for (int i = 1; i < n; i++)
		for (int j = i + 1; j <= n; j++)
			 k.push_back({get_distance(i, j), i, j});
	
	sort(k.begin(), k.end());

	int ind = 0;
	for (auto x : k){
		ll s = we(x); 
		int i = u(x), j = v(x);
		if (!uf.same(i, j))
			a[ind] = i, b[ind] = j, w[ind] = s, ind++, uf.unite(i, j);
	}
}

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