제출 #785038

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
785038		Charizard2021	City Mapping (NOI18_citymapping)	C++17	100 / 100	16 ms	8404 KiB

citymapping

#include<bits/stdc++.h>
#include "citymapping.h"
using namespace std;
const int N = 1000;
long long distances[N][N];
long long get_dst(int x, int y) {
	if (x > y) {
		swap(x, y);
	}
	auto &ret = distances[x][y];
	if (~ret){
		return ret;
	}
	return ret = get_distance(x + 1, y + 1);
}
long long &dist(int x, int y) {
	if (x > y) {
		swap(x, y);
	}
	return distances[x][y];
}
int sizeSubtree[N];
int counter;
vector<pair<int, int> > children[N];
bool visited[N];
vector<pair<int, int> > heavy;
void dfs(int u, int p) {
	sizeSubtree[u] = 1;
	counter++;
	for (pair<int, int> x : children[u]){
        int v = x.first;
		if (!visited[v]) {
			dist(p, v) = dist(p, u) + x.second;
			dfs(v, p);
			sizeSubtree[u] += sizeSubtree[v];
		}
	}
}
int dfs2(int u) {
	pair<int, int> maxVal = {-1, -1};
	for (pair<int, int> x : children[u]){
        int v = x.first;
		if (!visited[v] && (maxVal.first == -1 || sizeSubtree[maxVal.first] < sizeSubtree[v])) {
			maxVal = x;
		}
	}
	if (~maxVal.first) {
		heavy.push_back(maxVal);
		return dfs2(maxVal.first);
	}
	return u;
}
void find_roads(int n, int q, int a[], int b[], int w[]) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			distances[i][j] = -1;
		}
	}
	for (int i = 0; i < n; i++) {
		dist(i, i) = 0;
	}
	vector<pair<long long, int>> ds;
	for (int i = 1; i < n; i++) {
		ds.push_back({get_dst(0, i), i});
	}
	sort(ds.begin(), ds.end());
	int m = 0;
	for (auto &x: ds) {
		int r = 0;
		while (true) {
			counter = 0;
			dfs(r, r);
			if (counter == 1) {
				break;
			}
			int l = dfs2(r);
			long long xl = get_dst(x.second, l), rm = (get_dst(r, x.second) + get_dst(r, l) - xl) / 2;
			for (auto &y: heavy) {
				visited[y.first] = 1;
			}
			int i = 0;
			while (rm > 0) {
				rm -= heavy[i++].second;
			}
			int M = (i ? heavy[i - 1].first: r);
		    dist(M, x.second) = (get_dst(r, x.second) + get_dst(l, x.second) - get_dst(r, l)) / 2;
			heavy.clear();
			r = M;
		}
		a[m] = 1 + r;
        b[m] = 1 + x.second;
        w[m] = dist(r, x.second);
		children[r].push_back({b[m] - 1, w[m]});
		dist(r, b[m] - 1) = w[m];
		m++;
		for (int i = 0; i < n; i++) {
			visited[i] = 0;
		}
	}

}

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