Submission #953984

#	Time	Username	Problem	Language	Result	Execution time	Memory
953984		pcc	Truck Driver (IOI23_deliveries)	C++17	29 / 100	5541 ms	19760 KiB

deliveries

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

#define pii pair<int,int>
#define fs first
#define sc second
#define ll long long
#define pll pair<ll,ll>

const int mxn = 1e5+10;
vector<pii> tree[mxn];
ll W[mxn],sz[mxn],dep[mxn];

void init(int N, std::vector<int> U, std::vector<int> V, std::vector<int> t, std::vector<int> w) {
	for(int i = 0;i<N-1;i++){
		int a = U[i],b = V[i],c = t[i];
		tree[a].push_back(pll(b,c));
		tree[b].push_back(pll(a,c));
	}
	for(int i = 0;i<N;i++)W[i] = w[i];
	W[0] += 1;
	return;
}

void szdfs(int now,int par){
	sz[now] = W[now];
	for(auto nxt:tree[now]){
		if(nxt.fs == par)continue;
		szdfs(nxt.fs,now);
		sz[now] += sz[nxt.fs];
	}
	return;
}

int find_centroid(int now,int par,int tar){
	for(auto nxt:tree[now]){
		if(nxt.fs == par)continue;
		if(sz[nxt.fs]>tar)return find_centroid(nxt.fs,now,tar);
	}
	return now;
}

ll dfs1(int now,int par){
	ll re = 0;
	re += W[now]*dep[now];
	for(auto nxt:tree[now]){
		if(nxt.fs == par)continue;
		dep[nxt.fs] = dep[now]+nxt.sc;
		re += dfs1(nxt.fs,now);
	}
	return re;
}

long long max_time(int S, int X) {
	if(!S)X += 1;
	W[S] = X;
	szdfs(0,0);
	int cen = find_centroid(0,0,(sz[0])/2);
	dep[cen] = 0;
	return dfs1(cen,cen)*2;
}

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