Submission #917076

#	Time	Username	Problem	Language	Result	Execution time	Memory
917076		penguin133	Truck Driver (IOI23_deliveries)	C++17	29 / 100	1039 ms	60832 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;
	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);
	}
}
/*
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) {
	
	root->upd(S, X);
	sm += X - w[S];
	w[S] = X;
	if(sm%2){
		int lo = 0, hi = n - 1, ans = -1;
		while(lo <= hi){
			int mid = (lo + hi) >> 1;
			if(root->qry(mid, n - 1).fi >= (sm + 1) / 2)ans = mid, lo = mid + 1;
			else hi = mid - 1;
		}
		lo = 0, hi = n - 1; int ans2 = hi + 1;
		while(lo <= hi){
			int mid = (lo + hi) >> 1;
			if(root->qry(0, mid).fi >= (sm + 1) / 2)ans2 = mid, hi = mid - 1;
			else lo = mid + 1;
		}
		//ans is the midpoint
		//cout << ans << ' ' << ans2 << '\n';
		pi tmp = root->qry(ans + 1, n - 1), tmp2 = root->qry(0, ans - 1);
		ll cur = 2 * (tmp.se - tmp2.se);
		cur += 2 * ((sm / 2 - tmp.fi) * dist[ans] - (sm / 2 - tmp2.fi) * dist[ans]);
		cur += 2 * dist[ans2];
		return cur;
	}
	else{
		int lo = 0, hi = n - 1, ans = -1;
		while(lo <= hi){
			int mid = (lo + hi) >> 1;
			if(root->qry(mid, n - 1).fi >= (sm + 1) / 2)ans = mid, lo = mid + 1;
			else hi = mid - 1;
		}
		lo = 0, hi = n - 1; int ans2 = hi + 1;
		while(lo <= hi){
			int mid = (lo + hi) >> 1;
			if(root->qry(0, mid).fi >= sm / 2)ans2 = mid, hi = mid - 1;
			else lo = mid + 1;
		}
		//cout << ans << ' ' << ans2 << '\n';
		//ans is the midpoint
		pi tmp = root->qry(ans + 1, n - 1), tmp2 = root->qry(0, ans - 1);
		ll cur = 2 * (tmp.se - tmp2.se);
		cur += 2 * ((sm / 2 - tmp.fi) * dist[ans] - (sm / 2 - tmp2.fi) * dist[ans]);
		cur += 2 * dist[ans2];
		return cur;
	}
	return 0;
	
	/*
	int tmp = S;
	do{
		tot[tmp] += X - w[S];
		sm[tmp] += (X - w[S]) * dist[S];
		tmp /= 2;
	}while(tmp);
	int bruh = 0, ext = 0, cur = 0;
	while(1){
		if(adj[bruh].empty())
	}
	*/
}

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