#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){
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;
}
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
71 ms |
12164 KB |
3rd lines differ - on the 1st token, expected: '39049160', found: '39049014' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4956 KB |
Output is correct |
| 2 |
Correct |
9 ms |
4952 KB |
Output is correct |
| 3 |
Correct |
11 ms |
5208 KB |
Output is correct |
| 4 |
Correct |
17 ms |
4956 KB |
Output is correct |
| 5 |
Correct |
15 ms |
4956 KB |
Output is correct |
| 6 |
Correct |
16 ms |
5124 KB |
Output is correct |
| 7 |
Correct |
15 ms |
4956 KB |
Output is correct |
| 8 |
Correct |
15 ms |
4956 KB |
Output is correct |
| 9 |
Correct |
15 ms |
4956 KB |
Output is correct |
| 10 |
Incorrect |
3 ms |
5208 KB |
3rd lines differ - on the 1st token, expected: '28357342', found: '28291468' |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
71 ms |
12164 KB |
3rd lines differ - on the 1st token, expected: '39049160', found: '39049014' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
71 ms |
12164 KB |
3rd lines differ - on the 1st token, expected: '39049160', found: '39049014' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
71 ms |
12164 KB |
3rd lines differ - on the 1st token, expected: '39049160', found: '39049014' |
| 2 |
Halted |
0 ms |
0 KB |
- |
