Submission #1370583

#TimeUsernameProblemLanguageResultExecution timeMemory
1370583kaiboyDesignated Cities (JOI19_designated_cities)C++20
0 / 100
2095 ms18516 KiB
#include <algorithm>
#include <iostream>

using namespace std;

const       int   N = 200000;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;

int *ej[N], *ew[N], eo[N];
long long ss[N], s_, ans[N + 1];

void append(int i, int j, int w) {
	int o = eo[i]++;
	if (!o) {
		ej[i] = (int *) malloc(sizeof *ej[i]);
		ew[i] = (int *) malloc(sizeof *ew[i]);
	} else {
		ej[i] = (int *) realloc(ej[i], (o << 1) * sizeof *ej[i]);
		ew[i] = (int *) realloc(ew[i], (o << 1) * sizeof *ew[i]);
	}
	ej[i][o] = j;
	ew[i][o] = w;
}

void dfs(int p, int i, long long s) {
	ss[i] = s;
	for (int o = 0; o < eo[i]; o++) {
		int j = ej[i][o], w = ew[i][o];
		if (j != p)
			s_ += w, dfs(i, j, s + w);
	}
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n; cin >> n;
	for (int h = 0; h < n - 1; h++) {
		int i, j, w, w_; cin >> i >> j >> w >> w_, i--, j--;
		append(i, j, w), append(j, i, w_);
	}
	long long x_ = ans[1] = INF; int i_ = -1, j_ = -1;
	for (int i = 0; i < n; i++) {
		s_ = 0, dfs(-1, i, 0);
		ans[1] = min(ans[1], s_);
		for (int j = 0; j < n; j++) {
			long long x = s_ - ss[j];
			if (x_ > x)
				x_ = x, i_ = i, j_ = j;
		}
	}
	ans[2] = x_;
	int q; cin >> q;
	while (q--) {
		int k; cin >> k;
		cout << ans[k] << '\n';
	}
	return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...