Submission #114392

#	Time	Username	Problem	Language	Result	Execution time	Memory
114392		Mamnoon_Siam	Designated Cities (JOI19_designated_cities)	C++17	39 / 100	771 ms	132996 KiB

designated_cities

#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] + dp2[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] + 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 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 17 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44