oj.uz

Submission #1068612

# Submission time Handle Problem Language Result Execution time Memory
1068612 2024-08-21T10:55:49 Z new_acc Truck Driver (IOI23_deliveries) C++17
29 / 100
 513 ms 40820 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);
    int ost=0;
    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];
            ost=a;
        }else a=gora[a];
    }
    if(ost!=1){
        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);
    //cout<<dwa<<" "<<pom<<"\n";
    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 113 ms 18256 KB Output is correct
2 Correct 119 ms 18060 KB Output is correct
3 Correct 107 ms 18076 KB Output is correct
4 Correct 102 ms 18000 KB Output is correct
5 Correct 152 ms 18260 KB Output is correct

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10844 KB Output is correct
2 Correct 3 ms 10844 KB Output is correct
3 Correct 4 ms 11004 KB Output is correct
4 Correct 4 ms 10844 KB Output is correct
5 Correct 5 ms 10844 KB Output is correct
6 Correct 3 ms 10876 KB Output is correct
7 Correct 3 ms 10844 KB Output is correct
8 Correct 4 ms 11096 KB Output is correct
9 Correct 4 ms 10844 KB Output is correct
10 Correct 4 ms 10876 KB Output is correct
11 Incorrect 4 ms 10844 KB 63rd lines differ - on the 1st token, expected: '1386154', found: '1533190'
12 Halted 0 ms 0 KB -

Subtask #3
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 18256 KB Output is correct
2 Correct 119 ms 18060 KB Output is correct
3 Correct 107 ms 18076 KB Output is correct
4 Correct 102 ms 18000 KB Output is correct
5 Correct 152 ms 18260 KB Output is correct
6 Incorrect 2 ms 10844 KB 25th lines differ - on the 1st token, expected: '186548', found: '192070'
7 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 18256 KB Output is correct
2 Correct 119 ms 18060 KB Output is correct
3 Correct 107 ms 18076 KB Output is correct
4 Correct 102 ms 18000 KB Output is correct
5 Correct 152 ms 18260 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 4 ms 11100 KB Output is correct
8 Correct 30 ms 13592 KB Output is correct
9 Correct 450 ms 37876 KB Output is correct
10 Correct 449 ms 37680 KB Output is correct
11 Correct 513 ms 37888 KB Output is correct
12 Correct 436 ms 40780 KB Output is correct
13 Correct 354 ms 40820 KB Output is correct
14 Correct 320 ms 37188 KB Output is correct

Subtask #5
0.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 18256 KB Output is correct
2 Correct 119 ms 18060 KB Output is correct
3 Correct 107 ms 18076 KB Output is correct
4 Correct 102 ms 18000 KB Output is correct
5 Correct 152 ms 18260 KB Output is correct
6 Correct 4 ms 10844 KB Output is correct
7 Correct 3 ms 10844 KB Output is correct
8 Correct 4 ms 11004 KB Output is correct
9 Correct 4 ms 10844 KB Output is correct
10 Correct 5 ms 10844 KB Output is correct
11 Correct 3 ms 10876 KB Output is correct
12 Correct 3 ms 10844 KB Output is correct
13 Correct 4 ms 11096 KB Output is correct
14 Correct 4 ms 10844 KB Output is correct
15 Correct 4 ms 10876 KB Output is correct
16 Incorrect 4 ms 10844 KB 63rd lines differ - on the 1st token, expected: '1386154', found: '1533190'
17 Halted 0 ms 0 KB -