Submission #856936

#	Time	Username	Problem	Language	Result	Execution time	Memory
856936		Edu175	Truck Driver (IOI23_deliveries)	C++17	29 / 100	5538 ms	23088 KiB

deliveries

#include "deliveries.h"
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,ioi=b;i<ioi;i++)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define imp(v) for(auto asd:v)cout<<asd<<" ";cout<<"\n"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const ll MAXN=1e5+5;

ll n;
vector<ii>g[MAXN];
ll tot=1; //extra zero (return)

ll t[MAXN],c[MAXN];
ll res=0;

void dfs(ll x, ll f){
	c[x]=t[x];
	for(auto [y,w]:g[x])if(y!=f){
		dfs(y,x);
		res+=2*w*min(c[y],tot-c[y]);
		c[x]+=c[y];
	}
}

void init(int N, std::vector<int> u, std::vector<int> v, std::vector<int> w, std::vector<int> T) {
	n=N;
	fore(i,0,SZ(u)){
		g[u[i]].pb({v[i],w[i]});
		g[v[i]].pb({u[i],w[i]});
	}
	fore(i,0,n)t[i]=T[i],tot+=t[i];
}

long long max_time(int s, int x) {
	tot+=-t[s]+x;
	t[s]=x;
	res=0;
	dfs(0,-1);
	return res;
}

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