Submission #916121

#	Time	Username	Problem	Language	Result	Execution time	Memory
916121		emptypringlescan	Truck Driver (IOI23_deliveries)	C++17	50 / 100	5547 ms	56200 KiB

deliveries

#include <bits/stdc++.h>
using namespace std;
#include "deliveries.h"
vector<pair<int,long long> > adj[100005];
long long subsz[100005],arr[100005],ans;
void fsz(int x, int p){
	subsz[x]=arr[x];
	for(pair<int,long long> i:adj[x]){
		if(i.first==p) continue;
		fsz(i.first,x);
		subsz[x]+=subsz[i.first];
	}
}
void dfs(int x, int p){
	for(pair<int,long long> i:adj[x]){
		if(i.first==p) continue;
		ans+=i.second*min(subsz[i.first],1+subsz[0]-subsz[i.first]);
		dfs(i.first,x);
	}
}
long long pref[100005];
struct noode{
	int s,e,m;
	long long val;
	noode *l, *r;
	noode(int S, int E){
		s=S; e=E; m=(s+e)/2;
		if(s!=e){
			l=new noode(s,m);
			r=new noode(m+1,e);
			val=l->val+r->val;
		}
		else{
			val=arr[s];
		}
	}
	void update(int S, long long V){
		if(s==e){
			val+=V;
			return;
		}
		if(S<=m) l->update(S,V);
		else r->update(S,V);
		val=l->val+r->val;
	}
	int bsta(long long V){
		if(s==e) return s;
		if(l->val>V) return l->bsta(V);
		else return r->bsta(V-l->val);
	}
} *r1;
struct node{
	int s,e,m;
	long long val,lazy;
	node *l, *r;
	node(int S, int E){
		s=S; e=E; m=(s+e)/2;
		val=lazy=0;
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	void prop(){
		if(lazy==0||s==e) return;
		l->val+=lazy*(pref[m]-pref[s-1]);
		l->lazy+=lazy;
		r->val+=lazy*(pref[e]-pref[m]);
		r->lazy+=lazy;
		lazy=0;
	}
	void update(int S, int E, long long V){
		if(S<=s&&e<=E){
			val+=V*(pref[e]-pref[s-1]);
			lazy+=V;
			return;
		}
		prop();
		if(E<=m) l->update(S,E,V);
		else if(S>m) r->update(S,E,V);
		else l->update(S,m,V),r->update(m+1,E,V);
		val=l->val+r->val;
	}
	long long query(int S, int E){
		if(S<=s&&e<=E) return val;
		prop();
		if(E<=m) return l->query(S,E);
		else if(S>m) return r->query(S,E);
		else return l->query(S,m)+r->query(m+1,E);
	}
} *r2,*r3;
int st=1,n;
long long tot;
void init(int N, vector<int> u, vector<int> v, vector<int> t, vector<int> w){
	n=N;
	bool can=true;
	for(int i=0; i<n-1; i++){
		if(u[i]!=i||v[i]!=i+1) can=false;
		adj[u[i]].push_back({v[i],t[i]});
		adj[v[i]].push_back({u[i],t[i]});
	}
	if(can){
		st=4;
		for(int i=0; i<n-1; i++) pref[i+1]=pref[i]+t[i];
		pref[n]=pref[n-1];
	}
	for(int i=0; i<n; i++){
		arr[i]=w[i];
		tot+=w[i];
	}
	if(can){
		arr[0]++;
		r1=new noode(0,n-1);
		r2=new node(1,n-1);
		r3=new node(1,n-1);
		for(int i=0; i<n; i++){
			if(i<n-1) r2->update(i+1,n-1,arr[i]);
			if(i) r3->update(1,i,arr[i]);
		}
	}
}
long long max_time(int s, int x){
	if(st==1){
		arr[s]=x;
		fsz(0,-1);
		ans=0;
		dfs(0,-1);
		return ans*2ll;
	}
	if(s==0) x++;
	long long cha=x-arr[s];
	arr[s]=x;
	tot+=cha;
	r1->update(s,cha);
	if(s<n-1) r2->update(s+1,n-1,cha);
	if(s) r3->update(1,s,cha);
	int mid=r1->bsta(tot/2);
	long long ret=0;
	if(mid) ret+=r2->query(1,mid);
	if(mid<n-1) ret+=r3->query(mid+1,n-1);
	return ret*2ll;
}

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