Submission #917406

#	Time	Username	Problem	Language	Result	Execution time	Memory
917406		pavement	Truck Driver (IOI23_deliveries)	C++17	29 / 100	5567 ms	23320 KiB

deliveries

#include "deliveries.h"
#include <bits/stdc++.h>
using namespace std;

#define eb emplace_back

using ll = long long;
using ii = pair<int, int>;

ll ans, tot_W;
vector<int> W;
vector<ii> adj[100005];

ll dfs(int u, int e = -1) {
	ll ret = W[u];
	for (auto [v, w] : adj[u]) if (v != e) {
		auto tmp = dfs(v, u);
		ret += tmp;
		ans += min(tmp, tot_W - tmp + 1) * w;
	}
	return ret;
}

void init(int N, vector<int> U, vector<int> V, vector<int> T, vector<int> W) {
	for (int i = 0; i < N - 1; i++) {
		adj[U[i]].eb(V[i], T[i]);
		adj[V[i]].eb(U[i], T[i]);
	}
	::W = W;
	for (auto i : W) {
		tot_W += i;
	}
}

ll max_time(int S, int X) {
	tot_W += X - W[S];
	W[S] = X;
	ans = 0;
	dfs(0);
	return ans * 2;
}

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