Submission #1088389

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088389		tht2005	Designated Cities (JOI19_designated_cities)	C++17	16 / 100	145 ms	34132 KiB

designated_cities

#include <bits/stdc++.h>
using namespace std;

typedef pair<long long, int> pi;

struct edge_t {
	int to, w, w_rev;
	edge_t(int x, int y, int z) : to(x), w(y), w_rev(z) {}
};

const int N = (int)2e5 + 10;

int n;
vector<edge_t> aj[N];
long long ans[N], r1[N];

pi dfs3(int v, int p, tuple<long long, int, int>& res) {
	pi mx(r1[v], v), mx2(-1, -1);
	for(const edge_t& e : aj[v]) {
		if(e.to == p)
			continue;
		pi tmp = dfs3(e.to, v, res);
		tmp.first += e.w + e.w_rev;
		if(mx < tmp)
			mx2 = mx, mx = tmp;
		else if(mx2 < tmp)
			mx2 = tmp;
	}
	if(mx2.first != -1 && get<0> (res) < mx.first + mx2.first) {
		res = { mx.first + mx2.first, mx.second, mx2.second };
	}
	return mx;
}
void solve2() {
	tuple<long long, int, int> res = { -1, -1, -1 };
	dfs3(1, -1, res);
	ans[2] = get<0> (res) / 2;
}

void dfs2(int v, int p, long long val) {
	for(const edge_t& e : aj[v]) {
		if(e.to == p)
			continue;
		dfs2(e.to, v, val + r1[v] - r1[e.to] - e.w_rev + e.w);
	}
	r1[v] += val;
}
void dfs1(int v, int p) {
	r1[v] = 0;
	for(const edge_t& e : aj[v]) {
		if(e.to == p)
			continue;
		dfs1(e.to, v);
		r1[v] += r1[e.to] + e.w_rev;
	}
}
void solve1() {
	dfs1(1, -1);
	dfs2(1, -1, 0);
	ans[1] = *max_element(r1 + 1, r1 + 1 + n);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	long long tot = 0;
	for(int i = 1, u, v, x, y; i < n; ++i) {
		cin >> u >> v >> x >> y;
		aj[u].emplace_back(v, x, y);
		aj[v].emplace_back(u, y, x);
		tot += x + y;
	}
	solve1();
	solve2();
	int q;
	cin >> q;
	while(q--) {
		int i;
		cin >> i;
		cout << tot - ans[i] << '\n';
	}
	return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44