oj.uz

Submission #114379

# Submission time Handle Problem Language Result Execution time Memory
114379 2019-06-01T06:55:29 Z Mamnoon_Siam Designated Cities (JOI19_designated_cities) C++17
0 / 100
 2000 ms 28788 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[])
{
	freopen("in", "r", stdin);
	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;
}

Compilation message

designated_cities.cpp: In function 'int main(int, const char**)':
designated_cities.cpp:61:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("in", "r", stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2029 ms 28132 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2028 ms 28144 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2058 ms 28788 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2029 ms 28132 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2028 ms 28144 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2029 ms 28132 KB Time limit exceeded
2 Halted 0 ms 0 KB -