oj.uz

Submission #122870

# Submission time Handle Problem Language Result Execution time Memory
122870 2019-06-29T12:23:03 Z MvC Designated Cities (JOI19_designated_cities) C++17
7 / 100
 910 ms 123292 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];
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[magic + 15];
	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 <= min(magic, sz[u]); a++) {
			for(int b = 1; b <= min(magic, sz[v]); b++) {
				dp1[u][a + b] = max(dp1[u][a + b], dp2[u][a] + dp1[v][b] + w);
			}
		}
		for(int i = 0; i <= min(magic, sz[u] + sz[v]); i++)
			tmp[i] = 0;
		for(int a = 0; a <= min(sz[u], magic); a++) {
			for(int b = 1; b <= min(sz[v], magic); b++) {
				tmp[a + b] = max(tmp[a + b], dp2[u][a] + dp1[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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB Output is correct
2 Incorrect 15 ms 14972 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 14 ms 14584 KB Output is correct
2 Correct 839 ms 97284 KB Output is correct
3 Correct 910 ms 122796 KB Output is correct
4 Correct 763 ms 97356 KB Output is correct
5 Correct 832 ms 97392 KB Output is correct
6 Correct 866 ms 100728 KB Output is correct
7 Correct 814 ms 97644 KB Output is correct
8 Correct 899 ms 123292 KB Output is correct
9 Correct 757 ms 97980 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14584 KB Output is correct
2 Correct 839 ms 97284 KB Output is correct
3 Correct 910 ms 122796 KB Output is correct
4 Correct 763 ms 97356 KB Output is correct
5 Correct 832 ms 97392 KB Output is correct
6 Correct 866 ms 100728 KB Output is correct
7 Correct 814 ms 97644 KB Output is correct
8 Correct 899 ms 123292 KB Output is correct
9 Correct 757 ms 97980 KB Output is correct
10 Correct 14 ms 14456 KB Output is correct
11 Incorrect 826 ms 96792 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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