Submission #1226397

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226397		chaeryeong	Truck Driver (IOI23_deliveries)	C++20	29 / 100	90 ms	7752 KiB

deliveries

#include "deliveries.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector <pair <int, ll>> adj[1001];
ll t[1001], sum[1001];
void init (int n, vector <int> u, vector <int> v, vector <int> w, vector <int> T) {
	for (int i = 0; i < n; i++) {
		t[i] = T[i];
	}
	for (int i = 0; i < n - 1; i++) {
		adj[u[i]].push_back({v[i], w[i]});
		adj[v[i]].push_back({u[i], w[i]});
	}
}
void calc (int pos, int par) {
	sum[pos] = t[pos];
	for (auto [j, w] : adj[pos]) {
		if (j != par) {
			calc(j, pos);
			sum[pos] += sum[j];
		}
	}
}
ll get (int pos, int par) {
	ll ret = 0;
	for (auto [j, w] : adj[pos]) {
		if (j != par) {
			ret += get(j, pos);
			ret += w * min(sum[j], sum[0] - sum[j]) * 2;
		}
	}
	for (auto [j, w] : adj[pos]) {
		if (j != par) {
			if (sum[j] * 2 > sum[0]) {
				ret += 2 * w;
			}
		}
	}
	return ret;
}
ll max_time (int s, int x) {
	t[s] = x;
	calc(0, -1);
	return get(0, -1);
}

• Subtask 1: 8 / 8
• Subtask 2: 21 / 21
• Subtask 3: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 36