Submission #1068602

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068602		jamjanek	Truck Driver (IOI23_deliveries)	C++17	8 / 100	69 ms	10124 KiB

deliveries

#include "deliveries.h"
#include<bits/stdc++.h>
using namespace std;
int n, i;
vector<pair<int,long long>>graf[100010];
vector<int>val;
long long dep[100010];
long long r[100010];
long long pom[100010];

void dfs1(int x, int o){
	r[x]=val[x];
	pom[x]=val[x]*dep[x];
	for(auto j: graf[x])
		if(j.first!=o){
			dfs1(j.first, x);
			r[x]+=r[j.first];
			pom[x]+=pom[j.first];
		}
}

void dfs0(int x, int o){
	for(auto j: graf[x])
		if(j.first!=o){
			dep[j.first]=dep[x]+j.second;
			dfs0(j.first,x);
		}
}
void init(int N, std::vector<int> U, std::vector<int> V, std::vector<int> T, std::vector<int> W) {
	n=N;
	for(i=0;i<n-1;i++)
		graf[U[i]].push_back({V[i], T[i]}),
		graf[V[i]].push_back({U[i], T[i]});
	val = W;
	dfs0(0,0);
	dfs1(0,0);
	return;
}

long long wynik;//suma lca dwoch kolejnych w ciagu

void dfs2(int x, int o, long long usu){
//	printf("%d: przed %lld  %d\n", x, wynik, usu);
	pair<long,long> best{-1,-1};
	for(auto j: graf[x]){
		if(j.first!=o)
			best=max(best, {r[j.first],j.first});
	}
	if(best.first==-1){
//		if(x==3)printf("  %lld\n", max(0ll, r[x]-usu-1));
		wynik+=dep[x]*2*max(0ll, r[x]-usu-1);
		return;
	}
	if(r[x]-best.first+usu+1>=best.first){
		wynik+=dep[x]*2*(max(0ll,r[x]-usu-1));
		return;
	}
//	wynik-=(r[x]-usu)*dep[x]*2;
	for(auto j: graf[x])
		if(j.first==best.second){
			dfs2(j.first,x, usu+r[x]-best.first);
		}
//	printf("%d: po %lld\n", x, wynik);
}

long long max_time(int S, int X) {
//	printf("pytanie\n");
	val[S] = X;
	wynik = 0;
	dfs1(0,0);
//	for(i=0;i<n;i++)printf("%d %lld %lld %lld\n", i, dep[i], r[i], pom[i]);
	dfs2(0,0,0);
	return pom[0]*2-wynik;
}

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