oj.uz

Submission #114383

# Submission time Handle Problem Language Result Execution time Memory
114383 2019-06-01T07:08:21 Z Mamnoon_Siam Designated Cities (JOI19_designated_cities) C++17
23 / 100
 102 ms 57108 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e3 + 5;
using ll = long long;

int n;
ll dp1[maxn][maxn], dp2[maxn][maxn];
int A[maxn], B[maxn];
ll C[maxn], D[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;
	ll tmp[maxn];
	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 a = 1; a <= sz[u]; a++) {
			for(int b = 1; b <= sz[v]; b++) {
				dp1[u][a + b] = max(dp1[u][a + b], dp2[u][a] + dp2[v][b] + w);
			}
		}
		for(int i = 0; i <= sz[u] + sz[v]; i++)
			tmp[i] = 0;
		for(int a = 0; a <= sz[u]; a++) {
			for(int b = 1; b <= sz[v]; b++) {
				tmp[a + b] = max(tmp[a + b], dp2[u][a] + dp2[v][b] + w);
			}
		}
		sz[u] += sz[v];
		for(int i = 0; i <= sz[u]; i++) {
			dp2[u][i] = max(dp2[u][i], tmp[i]);
		}
	}
}

int main(int argc, char const *argv[])
{
	cin >> n;
	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 2 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 2 ms 384 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Runtime error 16 ms 8448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Runtime error 8 ms 3584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 46 ms 12056 KB Output is correct
14 Correct 87 ms 42600 KB Output is correct
15 Correct 46 ms 12276 KB Output is correct
16 Correct 47 ms 11512 KB Output is correct
17 Correct 44 ms 11264 KB Output is correct
18 Correct 46 ms 11128 KB Output is correct
19 Correct 43 ms 11640 KB Output is correct
20 Correct 42 ms 9848 KB Output is correct
21 Correct 48 ms 14464 KB Output is correct
22 Correct 48 ms 12672 KB Output is correct
23 Correct 43 ms 9592 KB Output is correct
24 Correct 38 ms 2532 KB Output is correct
25 Correct 102 ms 57108 KB Output is correct
26 Correct 36 ms 888 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Runtime error 16 ms 8448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Runtime error 16 ms 8448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -