oj.uz

Submission #122872

# Submission time Handle Problem Language Result Execution time Memory
122872 2019-06-29T12:24:40 Z MvC Designated Cities (JOI19_designated_cities) C++11
39 / 100
 907 ms 120548 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int maxn = 2e5 + 5;
using ll = long long;
 
int magic;
int n;
vector<ll> dp1[maxn], dp2[maxn];
int A[maxn], B[maxn];
ll C[maxn], D[maxn],tmp[maxn];
ll pre[maxn];
vector<int> g[maxn];
ll tot_down = 0;
int sz[maxn];
 
int other(int id, int u) {
	return A[id] ^ B[id] ^ u;
}
 
ll cost(int id, int from, int to) {
	if(A[id] == from) return C[id];
	else return D[id];
}
 
void dfs(int u, int parent, ll prefix_sum) {
	pre[u] = prefix_sum;
	for(int i : g[u]) {
		int v = A[i] ^ B[i] ^ u;
		if(parent != v) {
			dfs(v, u, prefix_sum + cost(i, v, u) - cost(i, u, v));
		}
	}
	sz[u] = 1;
	for(int i : g[u]) {
		int v = A[i] ^ B[i] ^ u;
		if(v == parent) continue;
		ll w = cost(i, u, v);
		tot_down += w;
      for(int i = 0; i <= min(magic, sz[u] + sz[v]); i++)
			tmp[i] = 0;
		for(int a = 0; a <= min(magic, sz[u]); a++) {
			for(int b = 1; b <= min(magic, sz[v]); b++) {
				if(a)dp1[u][a + b] = max(dp1[u][a + b], dp2[u][a] + dp2[v][b] + w);
              tmp[a + b] = max(tmp[a + b], dp2[u][a] + dp2[v][b] + w);
			}
		}
		sz[u] += sz[v];
		for(int i = 0; i <= min(sz[u], magic); i++) {
			dp2[u][i] = max(dp2[u][i], tmp[i]);
		}
	}
}
 
int main(int argc, char const *argv[])
{
	cin >> n;
	if(n > 2000) magic = 5;
	else magic = 2e3 + 2;
	for(int i = 1; i <= n; i++) {
		dp1[i].assign(magic + 15, 0);
		dp2[i].assign(magic + 15, 0);
	}
	for(int i = 1; i < n; i++) {
		cin >> A[i] >> B[i] >> C[i] >> D[i];
		g[A[i]].emplace_back(i);
		g[B[i]].emplace_back(i);
	}
	dfs(1, -1, 0);
	int q; cin >> q;
	while(q--) {
		int k;
		cin >> k;
		ll ans = LLONG_MAX;
		for(int i = 1; i <= n; i++) {
			ans = min(ans, tot_down - dp1[i][min(k, sz[i])] + pre[i]);
		}
		ans = max(0LL, ans);
		cout << ans << endl;
	}
	return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14584 KB Output is correct
2 Correct 14 ms 14968 KB Output is correct
3 Correct 14 ms 14968 KB Output is correct
4 Correct 14 ms 14968 KB Output is correct
5 Correct 14 ms 14968 KB Output is correct
6 Correct 14 ms 14968 KB Output is correct
7 Correct 14 ms 14968 KB Output is correct
8 Correct 14 ms 14968 KB Output is correct
9 Correct 14 ms 14968 KB Output is correct
10 Correct 14 ms 14968 KB Output is correct
11 Correct 15 ms 14968 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14584 KB Output is correct
2 Correct 821 ms 96676 KB Output is correct
3 Correct 907 ms 116984 KB Output is correct
4 Correct 738 ms 96860 KB Output is correct
5 Correct 817 ms 96884 KB Output is correct
6 Correct 840 ms 99528 KB Output is correct
7 Correct 805 ms 97136 KB Output is correct
8 Correct 892 ms 117496 KB Output is correct
9 Correct 743 ms 97388 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB Output is correct
2 Correct 827 ms 96680 KB Output is correct
3 Correct 898 ms 120548 KB Output is correct
4 Correct 746 ms 96756 KB Output is correct
5 Correct 819 ms 96812 KB Output is correct
6 Correct 865 ms 100100 KB Output is correct
7 Correct 759 ms 97644 KB Output is correct
8 Correct 882 ms 109376 KB Output is correct
9 Correct 727 ms 97524 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14584 KB Output is correct
2 Correct 14 ms 14968 KB Output is correct
3 Correct 14 ms 14968 KB Output is correct
4 Correct 14 ms 14968 KB Output is correct
5 Correct 14 ms 14968 KB Output is correct
6 Correct 14 ms 14968 KB Output is correct
7 Correct 14 ms 14968 KB Output is correct
8 Correct 14 ms 14968 KB Output is correct
9 Correct 14 ms 14968 KB Output is correct
10 Correct 14 ms 14968 KB Output is correct
11 Correct 15 ms 14968 KB Output is correct
12 Correct 14 ms 14456 KB Output is correct
13 Correct 123 ms 77812 KB Output is correct
14 Correct 136 ms 77916 KB Output is correct
15 Correct 133 ms 77756 KB Output is correct
16 Correct 124 ms 77888 KB Output is correct
17 Correct 122 ms 77816 KB Output is correct
18 Correct 138 ms 77816 KB Output is correct
19 Correct 136 ms 77816 KB Output is correct
20 Correct 127 ms 77788 KB Output is correct
21 Correct 124 ms 77916 KB Output is correct
22 Correct 128 ms 77816 KB Output is correct
23 Correct 141 ms 77816 KB Output is correct
24 Correct 146 ms 77816 KB Output is correct
25 Correct 137 ms 77944 KB Output is correct
26 Correct 130 ms 77816 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14584 KB Output is correct
2 Correct 821 ms 96676 KB Output is correct
3 Correct 907 ms 116984 KB Output is correct
4 Correct 738 ms 96860 KB Output is correct
5 Correct 817 ms 96884 KB Output is correct
6 Correct 840 ms 99528 KB Output is correct
7 Correct 805 ms 97136 KB Output is correct
8 Correct 892 ms 117496 KB Output is correct
9 Correct 743 ms 97388 KB Output is correct
10 Correct 14 ms 14456 KB Output is correct
11 Correct 827 ms 96680 KB Output is correct
12 Correct 898 ms 120548 KB Output is correct
13 Correct 746 ms 96756 KB Output is correct
14 Correct 819 ms 96812 KB Output is correct
15 Correct 865 ms 100100 KB Output is correct
16 Correct 759 ms 97644 KB Output is correct
17 Correct 882 ms 109376 KB Output is correct
18 Correct 727 ms 97524 KB Output is correct
19 Correct 14 ms 14584 KB Output is correct
20 Incorrect 838 ms 97000 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14584 KB Output is correct
2 Correct 14 ms 14968 KB Output is correct
3 Correct 14 ms 14968 KB Output is correct
4 Correct 14 ms 14968 KB Output is correct
5 Correct 14 ms 14968 KB Output is correct
6 Correct 14 ms 14968 KB Output is correct
7 Correct 14 ms 14968 KB Output is correct
8 Correct 14 ms 14968 KB Output is correct
9 Correct 14 ms 14968 KB Output is correct
10 Correct 14 ms 14968 KB Output is correct
11 Correct 15 ms 14968 KB Output is correct
12 Correct 14 ms 14584 KB Output is correct
13 Correct 821 ms 96676 KB Output is correct
14 Correct 907 ms 116984 KB Output is correct
15 Correct 738 ms 96860 KB Output is correct
16 Correct 817 ms 96884 KB Output is correct
17 Correct 840 ms 99528 KB Output is correct
18 Correct 805 ms 97136 KB Output is correct
19 Correct 892 ms 117496 KB Output is correct
20 Correct 743 ms 97388 KB Output is correct
21 Correct 14 ms 14456 KB Output is correct
22 Correct 827 ms 96680 KB Output is correct
23 Correct 898 ms 120548 KB Output is correct
24 Correct 746 ms 96756 KB Output is correct
25 Correct 819 ms 96812 KB Output is correct
26 Correct 865 ms 100100 KB Output is correct
27 Correct 759 ms 97644 KB Output is correct
28 Correct 882 ms 109376 KB Output is correct
29 Correct 727 ms 97524 KB Output is correct
30 Correct 14 ms 14456 KB Output is correct
31 Correct 123 ms 77812 KB Output is correct
32 Correct 136 ms 77916 KB Output is correct
33 Correct 133 ms 77756 KB Output is correct
34 Correct 124 ms 77888 KB Output is correct
35 Correct 122 ms 77816 KB Output is correct
36 Correct 138 ms 77816 KB Output is correct
37 Correct 136 ms 77816 KB Output is correct
38 Correct 127 ms 77788 KB Output is correct
39 Correct 124 ms 77916 KB Output is correct
40 Correct 128 ms 77816 KB Output is correct
41 Correct 141 ms 77816 KB Output is correct
42 Correct 146 ms 77816 KB Output is correct
43 Correct 137 ms 77944 KB Output is correct
44 Correct 130 ms 77816 KB Output is correct
45 Correct 14 ms 14584 KB Output is correct
46 Incorrect 838 ms 97000 KB Output isn't correct
47 Halted 0 ms 0 KB -