oj.uz

Submission #1088389

# Submission time Handle Problem Language Result Execution time Memory
1088389 2024-09-14T10:18:27 Z tht2005 Designated Cities (JOI19_designated_cities) C++17
16 / 100
 145 ms 34132 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Incorrect 2 ms 4952 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 107 ms 21084 KB Output is correct
3 Correct 145 ms 32080 KB Output is correct
4 Correct 99 ms 19792 KB Output is correct
5 Correct 97 ms 21112 KB Output is correct
6 Correct 109 ms 22864 KB Output is correct
7 Correct 104 ms 21000 KB Output is correct
8 Correct 132 ms 32596 KB Output is correct
9 Correct 76 ms 21628 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 99 ms 21332 KB Output is correct
3 Correct 140 ms 34132 KB Output is correct
4 Correct 96 ms 19792 KB Output is correct
5 Correct 110 ms 21008 KB Output is correct
6 Correct 117 ms 23324 KB Output is correct
7 Correct 86 ms 21248 KB Output is correct
8 Correct 129 ms 28756 KB Output is correct
9 Correct 74 ms 21248 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Incorrect 2 ms 4952 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 107 ms 21084 KB Output is correct
3 Correct 145 ms 32080 KB Output is correct
4 Correct 99 ms 19792 KB Output is correct
5 Correct 97 ms 21112 KB Output is correct
6 Correct 109 ms 22864 KB Output is correct
7 Correct 104 ms 21000 KB Output is correct
8 Correct 132 ms 32596 KB Output is correct
9 Correct 76 ms 21628 KB Output is correct
10 Correct 2 ms 4952 KB Output is correct
11 Correct 99 ms 21332 KB Output is correct
12 Correct 140 ms 34132 KB Output is correct
13 Correct 96 ms 19792 KB Output is correct
14 Correct 110 ms 21008 KB Output is correct
15 Correct 117 ms 23324 KB Output is correct
16 Correct 86 ms 21248 KB Output is correct
17 Correct 129 ms 28756 KB Output is correct
18 Correct 74 ms 21248 KB Output is correct
19 Correct 2 ms 4956 KB Output is correct
20 Incorrect 110 ms 21268 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Incorrect 2 ms 4952 KB Output isn't correct
3 Halted 0 ms 0 KB -