oj.uz

Submission #916119

# Submission time Handle Problem Language Result Execution time Memory
916119 2024-01-25T10:41:25 Z emptypringlescan Truck Driver (IOI23_deliveries) C++17
29 / 100
 737 ms 62024 KB 
#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];
	}
  arr[0]++;
	if(can){
		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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 12176 KB Output is correct
2 Correct 73 ms 11916 KB Output is correct
3 Correct 72 ms 12112 KB Output is correct
4 Correct 71 ms 12112 KB Output is correct
5 Correct 78 ms 12368 KB Output is correct

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4956 KB 3rd lines differ - on the 1st token, expected: '1627540', found: '1637496'
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 12176 KB Output is correct
2 Correct 73 ms 11916 KB Output is correct
3 Correct 72 ms 12112 KB Output is correct
4 Correct 71 ms 12112 KB Output is correct
5 Correct 78 ms 12368 KB Output is correct
6 Incorrect 2 ms 4956 KB 3rd lines differ - on the 1st token, expected: '45306', found: '45852'
7 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 12176 KB Output is correct
2 Correct 73 ms 11916 KB Output is correct
3 Correct 72 ms 12112 KB Output is correct
4 Correct 71 ms 12112 KB Output is correct
5 Correct 78 ms 12368 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 4 ms 5208 KB Output is correct
8 Correct 35 ms 10076 KB Output is correct
9 Correct 647 ms 54368 KB Output is correct
10 Correct 663 ms 58988 KB Output is correct
11 Correct 722 ms 59064 KB Output is correct
12 Correct 719 ms 62024 KB Output is correct
13 Correct 737 ms 62004 KB Output is correct
14 Correct 345 ms 58160 KB Output is correct

Subtask #5
0.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 12176 KB Output is correct
2 Correct 73 ms 11916 KB Output is correct
3 Correct 72 ms 12112 KB Output is correct
4 Correct 71 ms 12112 KB Output is correct
5 Correct 78 ms 12368 KB Output is correct
6 Incorrect 2 ms 4956 KB 3rd lines differ - on the 1st token, expected: '1627540', found: '1637496'
7 Halted 0 ms 0 KB -