Submission #979736

#	Time	Username	Problem	Language	Result	Execution time	Memory
979736		nguyentunglam	Truck Driver (IOI23_deliveries)	C++17	29 / 100	5551 ms	21808 KiB

deliveries

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

int n;

long long sum;

vector<int> w;

vector<vector<pair<int, int> > > adj;

void init(int N, std::vector<int> U, std::vector<int> V, std::vector<int> T, std::vector<int> W) {
  n = N;
  w = W;
  adj.resize(n);
  for(int i = 0; i + 1 < n; i++) {
    adj[U[i]].emplace_back(V[i], T[i]);
    adj[V[i]].emplace_back(U[i], T[i]);
  }
  sum = accumulate(W.begin(), W.end(), 0LL);
}

long long max_time(int s, int x) {
  sum -= w[s];
  w[s] = x;
  sum += w[s];
  vector<long long> sz(n);
  long long ans = 0;
	auto dfs = [&] (auto self, int u, int p) -> void {
    sz[u] = w[u];
    for(auto &[v, c] : adj[u]) if (v != p) {
      self(self, v, u);
      sz[u] += sz[v];
      ans += 2LL * c * min(sum - sz[v] + 1, sz[v]);
    }
	};
	dfs(dfs, 0, 0);
	return ans;
}

#ifdef ngu

int main() {
  freopen ("task.inp", "r", stdin);
  freopen ("task.out", "w", stdout);
	int N, Q;
	assert(2 == scanf("%d %d", &N, &Q));
	std::vector<int> U(N - 1), V(N - 1);
	for(int j = 0; j + 1 < N; j++)
		assert (1 == scanf("%d", &U[j]));
	for(int j = 0; j + 1 < N; j++)
		assert (1 == scanf("%d", &V[j]));
	std::vector<int> T(N - 1);
	for(int j = 0; j + 1 < N; j++)
		assert (1 == scanf("%d", &T[j]));
	std::vector<int> W(N);
	for(int i = 0; i < N; i++)
		assert (1 == scanf("%d", &W[i]));
	std::vector<int> S(Q);
	std::vector<int> X(Q);
	for(int k = 0; k < Q; k++)
		assert (2 == scanf("%d %d", &S[k], &X[k]));

	fclose(stdin);

	init(N, U, V, T, W);
	std::vector<long long> res(Q);
	for(int k = 0; k < Q; k++)
		res[k] = max_time(S[k], X[k]);

	for(int k = 0; k < Q; k++)
		printf("%lld\n", res[k]);
	fclose(stdout);
	return 0;
}
#endif // ngu

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