Submission #883114

#	Time	Username	Problem	Language	Result	Execution time	Memory
883114		amunduzbaev	Truck Driver (IOI23_deliveries)	C++17	29 / 100	1087 ms	49740 KiB

deliveries

#include "deliveries.h"
 
#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef long long ll;
//~ #define int ll
 
const int N = 1e5 + 5;
int n, cur;
ll tot;
vector<vector<ar<int, 2>>> edges;
vector<int> w;
vector<ar<int, 2>> par;
vector<ll> sub;
 
struct ST{
	ll Max[N << 2], sum[N << 2], f[N << 2], b[N << 2];
	
	void set(int i, int v, int lx, int rx, int x){
		if(lx == rx) { 
			b[x] = v; return;
		}
		
		int m = (lx + rx) >> 1;
		if(i <= m) set(i, v, lx, m, x << 1);
		else set(i, v, m + 1, rx, x << 1 | 1);
		
		b[x] = b[x << 1] + b[x << 1 | 1];
	} void set(int i, int v) { set(i, v, 0, N, 1); }
	
	void push(int x, int lx, int rx){
		if(lx == rx) return;
		Max[x << 1] += f[x], Max[x << 1 | 1] += f[x];
		sum[x << 1] += b[x << 1] * f[x];
		sum[x << 1 | 1] += b[x << 1 | 1] * f[x];
		f[x << 1] += f[x], f[x << 1 | 1] += f[x];
		
		f[x] = 0;
	}
	
	void add(int l, int r, int v, int lx, int rx, int x){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			Max[x] += v;
			sum[x] += b[x] * v;
			f[x] += v;
			return;
		}
		
		int m = (lx + rx) >> 1;
		push(x, lx, rx);
		add(l, r, v, lx, m, x << 1);
		add(l, r, v, m + 1, rx, x << 1 | 1);
		
		Max[x] = max(Max[x << 1], Max[x << 1 | 1]);
		sum[x] = sum[x << 1] + sum[x << 1 | 1];
	} void add(int l, int r, int v) { add(l, r, v, 0, N, 1); }
	
	ll get(int l, int r, int lx, int rx, int x){
		if(lx > r || rx < l) return 0ll;
		if(lx >= l && rx <= r) return sum[x];
		
		int m = (lx + rx) >> 1;
		push(x, lx, rx);
		
		return get(l, r, lx, m, x << 1) + get(l, r, m + 1, rx, x << 1 | 1);
	} ll get(int l, int r) { return get(l, r, 0, N, 1) ; }
	
	ll get_(int l, int r, int lx, int rx, int x){
		if(lx > r || rx < l ) return 0ll;
		if(lx >= l && rx <= r) return Max[x];
		
		int m = (lx + rx) >> 1;
		push(x, lx, rx);
		
		return max(get_(l, r, lx, m, x << 1), get_(l, r, m + 1, rx, x << 1 | 1));
	} ll get_(int l, int r) { return get_(l, r, 0, N, 1); }
	
	int big(int v, int lx, int rx, int x){
		if(lx == rx) return lx;
		
		int m = (lx + rx) >> 1;
		push(x, lx, rx);
		
		if(Max[x << 1 | 1] >= v) return big(v, m + 1, rx, x << 1 | 1);
		else return big(v, lx, m, x << 1);
	}
	
	int big(int v) { return big(v, 0, N, 1); }
}tree;
 
vector<int> cnt, hev, head, pos, ver;
vector<ll> pref;
 
void init(int N, vector<int> u, vector<int> v, vector<int> t, vector<int> W) {
	w = W; n = N;
	edges.resize(n);
	sub.resize(n);
	par.resize(n);
	cnt.resize(n), hev.resize(n);
	head.resize(n), pos.resize(n), ver.resize(n);
	pref.resize(n);
	
	tot = 2;
	for(int i=0;i<n;i++) tot += w[i];
	
	for(int i=0;i + 1<n;i++){
		edges[u[i]].push_back({v[i], 2 * t[i]});
		edges[v[i]].push_back({u[i], 2 * t[i]});
	}
	
	function<void(int, int)> dfs = [&](int u, int p){
		sub[u] = w[u] + (u == 0) * 2;
		cnt[u] = 1, hev[u] = -1;
		
		for(auto [x, c] : edges[u]){
			if(x == p) continue;
			par[x] = {u, c};
			pref[x] = pref[u] + c;
			
			dfs(x, u);
			if(hev[u] == -1 || cnt[x] > cnt[hev[u]]) hev[u] = x;
			
			cnt[u] += cnt[x];
			sub[u] += sub[x];
		}
	};
	
	dfs(0, 0);
	
	int last = 0;
	function<void(int, int, int)> dec = [&](int u, int p, int P){
		pos[u] = last++, ver[pos[u]] = u, head[u] = P;
		if(~hev[u]){
			dec(hev[u], u, P);
		}
		
		for(auto [x, c] : edges[u]){
			if(x == p || x == hev[u]) continue;
			dec(x, u, x);
		}
	};
	
	dec(0, 0, 0);
	for(int i=0;i<n;i++){
		tree.set(pos[i], par[i][1]);
	}
	for(int i=0;i<n;i++){
		tree.add(pos[i], pos[i], sub[i]);
	}
	
	//~ for(int i=0;i<n;i++){
		//~ cout<<sub[i]<<" ";
	//~ } cout<<endl;
	//~ for(int i=0;i<n;i++){
		//~ cout<<par[i][1]<<" ";
	//~ } cout<<endl;
	//~ for(int i=0;i<n;i++){
		//~ cout<<tree.get(pos[i], pos[i])<<" ";
	//~ } cout<<endl;
	//~ for(int i=0;i<n;i++){
		//~ cout<<tree.get_(pos[i], pos[i])<<" ";
	//~ }
	//~ cout<<endl;
}
 
ll get(int u){
	ll res = 0;
	while(head[u]){
		res += tree.get(pos[head[u]], pos[u]);
		u = par[head[u]][0];
	}
	
	res += tree.get(pos[head[u]], pos[u]);
	return res;
}
 
void add(int u, int x){
	while(head[u]){
		tree.add(pos[head[u]], pos[u], x);
		u = par[head[u]][0];
	}
	
	tree.add(pos[head[u]], pos[u], x);
}
 
ll max_time(int s, int x) {
	x = -w[s] + x;
	tot += x;
	w[s] += x;
	
	add(s, x);
	
	//~ cout<<tot<<" "<<(tot + 1) / 2<<"\n";
	//~ for(int i=0;i<n;i++){
		//~ cout<<tree.get_(i, i)<<" ";
	//~ } cout<<"\n";
	
	//~ cout<<tree.Max[1]<<endl;
	//~ cout<<(tot + 1) / 2<<endl;
	//~ cout<<tree.big((tot + 1) / 2)<<endl;;
	
	int cen = ver[tree.big((tot + 1) / 2)];
	
	//~ cout<<cen<<" "<<tree.sum[1]<<" "<<(tot - 1) * pref[cen]<<" "<<get(cen)<<"\n";
	
	ll res = tree.sum[1] + (tot - 1) * pref[cen];
	res -= get(cen) * 2;
	
	return res;
}

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