제출 #917093

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
917093		penguin133	Truck Driver (IOI23_deliveries)	C++17	22 / 100	5523 ms	28072 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[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[i] = x;
		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] += (ll)X - w[S];
		shit[tmp] += 1ll * (X - w[S]) * dist[S];
		if(!tmp)break;
		tmp = par[tmp];
	}
	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 brr = 0, mx = 0;
		
		//ll x = bruh * 2 + 1, y = bruh * 2 + 2;
		for(auto [i, j] : adj[bruh])brr += tot[i], mx = max(mx, tot[i]);
		if(mx - ext > brr - mx){
			ll bruh2 = 0;
			for(auto [i, j] : adj[bruh])bruh2 += shit[i];
          int go = -1;
			for(auto [i, j] : adj[bruh]){
				if(tot[i] == mx){
					bruh2 -= shit[i];
					cur += (bruh2 - (brr - mx) * dist[bruh]) * 2;
					cur += j * 2 * (brr - mx + ext);
					ext += brr - mx;
                  assert(go == -1);
					go = i;
				}
			}
          assert(go != -1);
          bruh = go;
		}
		else{
			brr = 0; ll brr2 = 0;
			for(auto [i, j] : adj[bruh])brr += shit[i], brr2 += tot[i];
			cur += (brr - brr2 * 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