#include "deliveries.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N=1e5+5;
const int K=1<<18;
int n;
vector<pair<int,int>> adj[N];
int sz[N],hv[N],head[N],tail[N],par[N],tin[N],tout[N],ord[N];
ll w[N],dist[N];
int timer;
ll tot,ans;
ll val[N];
set<pair<ll,int>> ch[N];
struct Fenwick{
ll t[N];
void update(int i,ll v){
for(;i<N;i+=i&-i)t[i]+=v;
}
ll query(int i){
ll res=0;
for(;i>0;i-=i&-i)res+=t[i];
return res;
}
ll query(int l,int r){
return query(r)-query(l-1);
}
}f;
struct SegTree{
ll t[K],lz[K];
void apply(int i,ll v){
t[i]+=v;
lz[i]+=v;
}
void push(int i){
apply(i*2,lz[i]);
apply(i*2+1,lz[i]);
lz[i]=0;
}
void update(int l,int r,int i,int x,int y,ll v){
if(y<l||r<x)return;
if(x<=l&&r<=y)return apply(i,v);
push(i);
int m=(l+r)/2;
update(l,m,i*2,x,y,v);
update(m+1,r,i*2+1,x,y,v);
t[i]=max(t[i*2],t[i*2+1]);
}
void update(int x,int y,ll v){
update(1,n,1,x,y,v);
}
ll findlast(int l,int r,int i,int x,int y,ll v){
if(y<l||r<x||t[i]<v)return 0;
if(l==r)return l;
push(i);
int m=(l+r)/2;
ll res=findlast(m+1,r,i*2+1,x,y,v);
if(res==0)res=findlast(l,m,i*2,x,y,v);
return res;
}
ll findlast(int x,int y,ll v){
return findlast(1,n,1,x,y,v);
}
}s;
void dfs(int u){
sz[u]=1;
for(auto [v,w]:adj[u])if(v!=par[u]){
par[v]=u;
dist[v]=dist[u]+w;
dfs(v);
sz[u]+=sz[v];
if(sz[v]>sz[hv[u]])hv[u]=v;
}
}
void hld(int u){
tin[u]=++timer;
ord[timer]=u;
if(!head[u])head[u]=u;
tail[head[u]]=u;
if(hv[u])head[hv[u]]=head[u],hld(hv[u]);
for(auto [v,w]:adj[u])if(v!=par[u]&&v!=hv[u])hld(v);
tout[u]=timer;
}
void update(int u,ll v){
tot+=v;
ans+=v*dist[u];
f.update(tin[u],v);
while(u){
s.update(tin[head[u]],tin[u],v);
u=head[u];
int p=par[u];
ch[p].erase({val[u],u});
val[u]+=v;
ch[p].emplace(val[u],u);
u=p;
}
}
int centroid(){
int u=1;
ll half=tot/2;
while(true){
u=ord[s.findlast(tin[head[u]],tin[tail[u]],half+1)];
if(ch[u].empty())break;
auto [w,v]=*ch[u].rbegin();
if(w<=half)break;
u=v;
}
return u;
}
ll calc(int u){
return ans+dist[u]*(tot-2*f.query(tin[u],tout[u]));
}
void init(int _n,vector<int> _u,vector<int> _v,vector<int> _t,vector<int> _w){
n=_n;
for(int i=0;i<n-1;i++){
int u=_u[i]+1,v=_v[i]+1,w=_t[i];
adj[u].emplace_back(v,w);
adj[v].emplace_back(u,w);
}
for(int i=0;i<n;i++)w[i+1]=_w[i];
w[1]++;
dfs(1);
hld(1);
for(int i=1;i<=n;i++)update(i,w[i]);
}
ll max_time(int s,int x){
s++;
update(s,-w[s]);
w[s]=x;
if(s==1)w[s]++;
update(s,w[s]);
return calc(centroid())*2;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
88 ms |
14852 KB |
Output is correct |
2 |
Correct |
92 ms |
14672 KB |
Output is correct |
3 |
Correct |
88 ms |
14928 KB |
Output is correct |
4 |
Correct |
87 ms |
14672 KB |
Output is correct |
5 |
Correct |
88 ms |
14836 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
7644 KB |
3rd lines differ - on the 1st token, expected: '1627540', found: '4052724' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
88 ms |
14852 KB |
Output is correct |
2 |
Correct |
92 ms |
14672 KB |
Output is correct |
3 |
Correct |
88 ms |
14928 KB |
Output is correct |
4 |
Correct |
87 ms |
14672 KB |
Output is correct |
5 |
Correct |
88 ms |
14836 KB |
Output is correct |
6 |
Incorrect |
4 ms |
7516 KB |
3rd lines differ - on the 1st token, expected: '45306', found: '59282' |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
88 ms |
14852 KB |
Output is correct |
2 |
Correct |
92 ms |
14672 KB |
Output is correct |
3 |
Correct |
88 ms |
14928 KB |
Output is correct |
4 |
Correct |
87 ms |
14672 KB |
Output is correct |
5 |
Correct |
88 ms |
14836 KB |
Output is correct |
6 |
Incorrect |
3 ms |
7464 KB |
3rd lines differ - on the 1st token, expected: '129238', found: '221794' |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
88 ms |
14852 KB |
Output is correct |
2 |
Correct |
92 ms |
14672 KB |
Output is correct |
3 |
Correct |
88 ms |
14928 KB |
Output is correct |
4 |
Correct |
87 ms |
14672 KB |
Output is correct |
5 |
Correct |
88 ms |
14836 KB |
Output is correct |
6 |
Incorrect |
3 ms |
7644 KB |
3rd lines differ - on the 1st token, expected: '1627540', found: '4052724' |
7 |
Halted |
0 ms |
0 KB |
- |