oj.uz

Submission #1068691

# Submission time Handle Problem Language Result Execution time Memory
1068691 2024-08-21T11:23:47 Z new_acc Truck Driver (IOI23_deliveries) C++17
100 / 100
 973 ms 35124 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 18056 KB Output is correct
2 Correct 90 ms 18004 KB Output is correct
3 Correct 110 ms 18260 KB Output is correct
4 Correct 104 ms 18000 KB Output is correct
5 Correct 98 ms 18256 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10844 KB Output is correct
2 Correct 3 ms 10844 KB Output is correct
3 Correct 4 ms 11012 KB Output is correct
4 Correct 3 ms 10844 KB Output is correct
5 Correct 4 ms 10844 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 4 ms 10844 KB Output is correct
8 Correct 5 ms 10904 KB Output is correct
9 Correct 5 ms 10856 KB Output is correct
10 Correct 4 ms 10840 KB Output is correct
11 Correct 4 ms 10844 KB Output is correct
12 Correct 4 ms 10844 KB Output is correct
13 Correct 4 ms 10844 KB Output is correct
14 Correct 3 ms 10844 KB Output is correct
15 Correct 3 ms 10844 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 18056 KB Output is correct
2 Correct 90 ms 18004 KB Output is correct
3 Correct 110 ms 18260 KB Output is correct
4 Correct 104 ms 18000 KB Output is correct
5 Correct 98 ms 18256 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 7 ms 10984 KB Output is correct
8 Correct 67 ms 12864 KB Output is correct
9 Correct 916 ms 29380 KB Output is correct
10 Correct 828 ms 29232 KB Output is correct
11 Correct 819 ms 29228 KB Output is correct
12 Correct 884 ms 30764 KB Output is correct
13 Correct 941 ms 30672 KB Output is correct
14 Correct 973 ms 30764 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 18056 KB Output is correct
2 Correct 90 ms 18004 KB Output is correct
3 Correct 110 ms 18260 KB Output is correct
4 Correct 104 ms 18000 KB Output is correct
5 Correct 98 ms 18256 KB Output is correct
6 Correct 2 ms 10840 KB Output is correct
7 Correct 4 ms 11100 KB Output is correct
8 Correct 30 ms 13164 KB Output is correct
9 Correct 391 ms 33364 KB Output is correct
10 Correct 455 ms 32824 KB Output is correct
11 Correct 401 ms 33328 KB Output is correct
12 Correct 317 ms 35116 KB Output is correct
13 Correct 334 ms 35124 KB Output is correct
14 Correct 298 ms 33248 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 18056 KB Output is correct
2 Correct 90 ms 18004 KB Output is correct
3 Correct 110 ms 18260 KB Output is correct
4 Correct 104 ms 18000 KB Output is correct
5 Correct 98 ms 18256 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 3 ms 10844 KB Output is correct
8 Correct 4 ms 11012 KB Output is correct
9 Correct 3 ms 10844 KB Output is correct
10 Correct 4 ms 10844 KB Output is correct
11 Correct 3 ms 10844 KB Output is correct
12 Correct 4 ms 10844 KB Output is correct
13 Correct 5 ms 10904 KB Output is correct
14 Correct 5 ms 10856 KB Output is correct
15 Correct 4 ms 10840 KB Output is correct
16 Correct 4 ms 10844 KB Output is correct
17 Correct 4 ms 10844 KB Output is correct
18 Correct 4 ms 10844 KB Output is correct
19 Correct 3 ms 10844 KB Output is correct
20 Correct 3 ms 10844 KB Output is correct
21 Correct 2 ms 10844 KB Output is correct
22 Correct 7 ms 10984 KB Output is correct
23 Correct 67 ms 12864 KB Output is correct
24 Correct 916 ms 29380 KB Output is correct
25 Correct 828 ms 29232 KB Output is correct
26 Correct 819 ms 29228 KB Output is correct
27 Correct 884 ms 30764 KB Output is correct
28 Correct 941 ms 30672 KB Output is correct
29 Correct 973 ms 30764 KB Output is correct
30 Correct 2 ms 10840 KB Output is correct
31 Correct 4 ms 11100 KB Output is correct
32 Correct 30 ms 13164 KB Output is correct
33 Correct 391 ms 33364 KB Output is correct
34 Correct 455 ms 32824 KB Output is correct
35 Correct 401 ms 33328 KB Output is correct
36 Correct 317 ms 35116 KB Output is correct
37 Correct 334 ms 35124 KB Output is correct
38 Correct 298 ms 33248 KB Output is correct
39 Correct 3 ms 8796 KB Output is correct
40 Correct 4 ms 9088 KB Output is correct
41 Correct 39 ms 11224 KB Output is correct
42 Correct 560 ms 32332 KB Output is correct
43 Correct 550 ms 32668 KB Output is correct
44 Correct 598 ms 33112 KB Output is correct
45 Correct 507 ms 33156 KB Output is correct
46 Correct 511 ms 33324 KB Output is correct
47 Correct 410 ms 33928 KB Output is correct
48 Correct 391 ms 34348 KB Output is correct
49 Correct 386 ms 34584 KB Output is correct
50 Correct 373 ms 34604 KB Output is correct
51 Correct 323 ms 34860 KB Output is correct
52 Correct 652 ms 30512 KB Output is correct
53 Correct 590 ms 30472 KB Output is correct
54 Correct 643 ms 30512 KB Output is correct
55 Correct 297 ms 32044 KB Output is correct
56 Correct 361 ms 33564 KB Output is correct
57 Correct 347 ms 33584 KB Output is correct