Submission #917084

#	Time	Username	Problem	Language	Result	Execution time	Memory
917084		penguin133	Truck Driver (IOI23_deliveries)	C++17	22 / 100	174 ms	41672 KiB

deliveries

#include <bits/stdc++.h>
using namespace std;
 
#include "deliveries.h"
//#define int long long
typedef long long ll;
#define pi pair<ll, ll>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
vector <int> t, w, u, v;
ll dist[300005];
 
struct node{
	int s, e, m; ll val, val2;
	node *l, *r;
	node(int _s, int _e){
		s = _s, e = _e, m = (s + e) >> 1;
		if(s != e)l = new node(s, m), r = new node(m+1, e);
		val = val2 = 0;
	}
	
	void upd(int p, ll v){
		if(s == e){
			val = v;
			val2 = v * dist[p];
			return;
		}
		if(p <= m)l->upd(p, v);
		else r->upd(p, v);
		val = l->val + r->val;
		val2 = l->val2 + r->val2;
	}
	
	pi qry(int a, int b){
		if(a > b)return {0, 0};
		if(s == a && b == e)return {val,val2};
		if(b <= m)return l->qry(a, b);
		if(a > m)return r->qry(a ,b);
		pi lft = l->qry(a, m), rgt = r->qry(m+1, b);
		return {lft.fi + rgt.fi, lft.se + rgt.se};
	}
}*root;
ll n, sm, par[20][100005], shit[100005], tot[100005], cnt = 0;
vector <pi> adj[100005];
void dfs(int x, ll cur){
	dist[x] = cur;
	tot[x] = w[x], shit[x] = dist[x] * w[x];
	for(auto [i, j] : adj[x]){
		par[0][i] = x;
		for(int k = 1; k <= 19; k++)par[k][i] = par[k-1][par[k-1][i]];
		dfs(i, cur + j);
		tot[x] += tot[i];
		shit[x] += shit[i];
	}
}
/*
int lca(int u, int v){
	if(dep[u] > dep[v])swap(u, v);
	int df = dep[v] - dep[u];
	for(int i = 0; i <= 19; i++)if(df >> i & 1)v = par[i][v];
	if(u == v)return u;
	for(int i = 19; i >= 0; i--)if(par[i][u] != par[i][v])u = par[i][u], v = par[i][v];
	return par[0][u];
}
*/
 
void init(int N, std::vector<int> U, std::vector<int> V, std::vector<int> T, std::vector<int> W) {
	u = U; v = V; t = T; w = W;
	for(int i = 0; i < N - 1; i++)adj[U[i]].push_back({V[i], T[i]});
	dfs(0, 0);
	//for(int i = 0; i < N; i++)back[S[i]] = i;
	//for(int i = 1; i < N; i++)dist[i] = dist[i - 1] + t[i - 1];
	//root = new node(0, N - 1);
	n = N;
	//for(int i = 0; i < N; i++)root->upd(i, w[i]), sm += w[i];
	return;
}
 
long long max_time(int S, int X) {
	
	int tmp = S;
	while(1){
		tot[tmp] += X - w[S];
		shit[tmp] += (X - w[S]) * dist[S];
		if(!tmp)break;
		tmp = (tmp - 1) / 2;
	}
	w[S] = X;
	ll bruh = 0, ext = 0, cur = 0;
	while(1){
		ext += w[bruh];
		if(adj[bruh].empty()){
			cur += 2 * dist[bruh];
			break;
		}
		ll x = bruh * 2 + 1, y = bruh * 2 + 2;
		ll mx = max(tot[x], tot[y]), mn = min(tot[x], tot[y]);
		if(mx - ext <= mn){
			cur += ((shit[x] + shit[y]) - (tot[x] + tot[y]) * dist[bruh]) * 2 + 2 * dist[bruh];
			break;
		}
		if(tot[x] > tot[y]){
			cur += (shit[y] - tot[y] * dist[bruh]) * 2;
			cur += adj[bruh][0].se * 2 * (tot[y] + ext);
			ext += tot[y];
			bruh = x;
		}
		else{
			cur += (shit[x] - tot[x] * dist[bruh]) * 2;
			cur += adj[bruh][1].se * 2 * (tot[x] + ext);
			ext += tot[x];
			bruh = y;
		}
	}
	return cur;
}

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