oj.uz

답안 #114361

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
114361 2019-06-01T05:15:07 Z Mamnoon_Siam Designated Cities (JOI19_designated_cities) C++17
0 / 100
 15 ms 8568 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;
	for(int i : g[u]) if((A[i] ^ B[i] ^ u) != parent) {
		int v = A[i] ^ B[i] ^ u;
		int 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 b = 1; b <= sz[v]; b++) {
			for(int a = sz[u]; a >= 0; a--) {
				dp2[u][a + b] = max(dp2[u][a + b], dp2[u][a] + dp2[v][b] + w);
			}
		}
		sz[u] += sz[v];
	}
}

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]);
		}
		cout << ans << endl;
	}
	return 0;
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Runtime error 15 ms 8568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Runtime error 10 ms 3584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Runtime error 15 ms 8568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -