Submission #916098

#	Time	Username	Problem	Language	Result	Execution time	Memory
916098		emptypringlescan	Truck Driver (IOI23_deliveries)	C++17	29 / 100	5586 ms	27524 KiB

deliveries

#include <bits/stdc++.h>
using namespace std;
#include "deliveries.h"
vector<pair<int,long long> > adj[100005];
long long subsz[100005],arr[100005],ans;
void fsz(int x, int p){
	subsz[x]=arr[x];
	for(pair<int,long long> i:adj[x]){
		if(i.first==p) continue;
		fsz(i.first,x);
		subsz[x]+=subsz[i.first];
	}
}
void dfs(int x, int p){
	for(pair<int,long long> i:adj[x]){
		if(i.first==p) continue;
		ans+=i.second*min(subsz[i.first],1+subsz[0]-subsz[i.first]);
		dfs(i.first,x);
	}
}
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]].push_back({v[i],t[i]});
		adj[v[i]].push_back({u[i],t[i]});
	}
	for(int i=0; i<n; i++){
		arr[i]=w[i];
	}
}
long long max_time(int s, int x){
	arr[s]=x;
	fsz(0,-1);
	ans=0;
	dfs(0,-1);
	return ans*2ll;
}

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