Submission #1068691

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068691		new_acc	Truck Driver (IOI23_deliveries)	C++17	100 / 100	973 ms	35124 KiB

deliveries

#include "deliveries.h"
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef vector<ll> vl;
const int N=1e5+10;
const int SS=1<<17;
const int INFi=1e9;
ll seg1[SS*2+10],seg2[SS*2+10],kr[N],sc[N],sum,vmn[N],sk[N],cres;
int dol[N],gora[N],pod[N],li,t[N],n,odw[N],oj[N];
bool ci[N];
pair<int,int> pre[N];
set<pair<ll,int>> s;
vector<pair<int,int>> graf[N];
void upd1(int a,ll b){
    for(a+=SS;a>0;a/=2) seg1[a]+=b;
}
void upd2(int a,ll b){
    for(a+=SS;a>0;a/=2) seg2[a]+=b;
}
ll qr1(int a,int b){
    ll res=0;
    for(a+=SS-1,b+=SS+1;a/2!=b/2;a/=2,b/=2){
        if(a%2==0) res+=seg1[a+1];
        if(b%2) res+=seg1[b-1];
    }
    return res;
}
ll qr2(int a,int b){
    ll res=0;
    for(a+=SS-1,b+=SS+1;a/2!=b/2;a/=2,b/=2){
        if(a%2==0) res+=seg2[a+1];
        if(b%2) res+=seg2[b-1];
    }
    return res;
}
void dfs(int v,int o,int val){
    oj[v]=o;
    kr[v]=val;
    pod[v]=1;
    for(auto [u,c]:graf[v]){
        if(u==o) continue;
        sk[u]=sk[v]+c;
        dfs(u,v,c);
        pod[v]+=pod[u];
    }
}
void dfs2(int v,int o){
    int g=-1,g2=0;
    pre[v].fi=++li;
    odw[li]=v;
    dol[v]=v;
    if(ci[v]) gora[v]=gora[o];
    else gora[v]=v;
    for(auto [u,c]:graf[v]){
        if(u==o) continue;
        if(g==-1 or pod[u]>pod[g]) g=u,g2=c;
    }
    if(g!=-1){
        ci[g]=1;
        sc[g]=sc[v]+g2;
        dfs2(g,v);
        dol[v]=dol[g];
    }
    for(auto [u,c]:graf[v]){
        if(u==o or u==g) continue;
        dfs2(u,v);
    }
    pre[v].se=li;
}
void build(int v){
    if(v>=SS){
        int id=v-SS;
        if(id<=n and id>=1) seg1[v]=t[odw[id]];
    }else{
        build(v*2),build(v*2+1);
        seg1[v]=seg1[v*2]+seg1[v*2+1];
    }
}
void zm(int a,int b){
    ll r=b-t[a];
    t[a]=b;
    sum+=r;
    cres+=r*sk[a];
    upd1(pre[a].fi,r);
    if(ci[a]) upd2(pre[a].fi,r*sc[a]);
    while(a!=1){
        if(!ci[a]){
            upd2(pre[oj[a]].fi,r*sc[oj[a]]);
            s.erase({vmn[a],-pre[a].fi});
            vmn[a]+=r;
            s.insert({vmn[a],-pre[a].fi}); 
            a=oj[a];
        }else a=gora[a];
    }
    s.erase({vmn[a],-pre[a].fi});
    vmn[a]+=r;
    s.insert({vmn[a],-pre[a].fi}); 
}
int zn(){
    auto it=s.lower_bound(make_pair(sum/2+1,-INFi));
    if(it==s.end()) return -1;
    int v=odw[-(*it).se];
    int pocz=pre[v].fi,kon=pre[dol[v]].fi,sr,res=0;
    while(pocz<=kon){
        sr=(pocz+kon)/2;
        if(qr1(pre[odw[sr]].fi,pre[odw[sr]].se)>=sum/2+1){
            res=odw[sr];
            pocz=sr+1;
        }else kon=sr-1;
    }
    return res;
}
ll ob(int a){
    ll res=0;
    while(a!=1){
        if(ci[a]){
            res+=qr1(pre[a].fi,pre[a].se)*sc[a];
            res+=qr2(pre[gora[a]].fi,pre[a].fi-1);
            a=gora[a];
        }else{
            res+=vmn[a]*kr[a];
            a=oj[a];
        }
    }
    return res;
}
void init(int nn, std::vector<int> U, std::vector<int> V, std::vector<int> T, std::vector<int> W) {
    n=nn;
    for(int i=0;i<n-1;i++){
        graf[U[i]+1].push_back({V[i]+1,T[i]});
        graf[V[i]+1].push_back({U[i]+1,T[i]});
    }
    for(int i=0;i<n;i++) t[i+1]=W[i];     
    t[1]++;
    for(int i=1;i<=n;i++) sum+=t[i];
    dfs(1,1,0),dfs2(1,1);
    build(1);
    for(int i=1;i<=n;i++){
        ll xd=qr1(pre[i].fi,pre[i].se);
        cres+=kr[i]*xd;
        if(!ci[i]){
            vmn[i]=xd;
            s.insert({xd,-pre[i].fi});
            upd2(pre[oj[i]].fi,xd*sc[oj[i]]);
        }else{
            upd2(pre[i].fi,(ll)t[i]*sc[i]);
        }
    }
	return;
}

long long max_time(int S, int X) {
    if(S==0) X++;
    zm(S+1,X);
    int a=zn();
    if(a==-1) return cres*2LL;
    ll pom=ob(a);
    ll ans=cres-pom*2+sum*sk[a];
	return ans*2LL;
}

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