Submission #954122

#	Time	Username	Problem	Language	Result	Execution time	Memory
954122		Darren0724	Truck Driver (IOI23_deliveries)	C++17	29 / 100	5563 ms	25136 KiB

deliveries

#include "deliveries.h"
#include <bits/stdc++.h>
using namespace std;
const int N=100005;
long long tot=0,ans=0;
vector<int> sz(N),w;
vector<pair<int,int>> adj[N];
void dfs(int k,int pa,int t){
	sz[k]=w[k];
	for(auto [j,c]:adj[k]){
		if(j==pa)continue;
		dfs(j,k,c);
		sz[k]+=sz[j];
	}
	long long y=min(1ll*sz[k],tot-sz[k]);
	ans+=y*t*2;
}
void init(int N, vector<int> U, vector<int> V, vector<int> T, vector<int> W) {
	w=W;
	for(int i=0;i<N-1;i++){
		adj[U[i]].push_back({V[i],T[i]});
		adj[V[i]].push_back({U[i],T[i]});
	}
	for(int i=0;i<N;i++){
		tot+=w[i];
	}
	w[0]++;
	tot++;
	return;
}

long long max_time(int S, int X) {
	ans=0;
	X+=(S==0);
	tot-=w[S];
	w[S]=X;
	tot+=X;
	dfs(1,1,0);
	return ans;
}

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