oj.uz

Submission #1068544

# Submission time Handle Problem Language Result Execution time Memory
1068544 2024-08-21T10:32:35 Z new_acc Truck Driver (IOI23_deliveries) C++17
29 / 100
 413 ms 41012 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+1)/2,-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+1)/2){
            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 96 ms 20820 KB Output is correct
2 Correct 91 ms 20564 KB Output is correct
3 Correct 97 ms 20820 KB Output is correct
4 Correct 94 ms 20616 KB Output is correct
5 Correct 88 ms 20820 KB Output is correct

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10844 KB Output is correct
2 Correct 4 ms 10844 KB Output is correct
3 Correct 3 ms 10844 KB Output is correct
4 Correct 4 ms 10844 KB Output is correct
5 Correct 3 ms 10868 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 10840 KB Output is correct
9 Correct 3 ms 10904 KB Output is correct
10 Correct 3 ms 10844 KB Output is correct
11 Incorrect 3 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 96 ms 20820 KB Output is correct
2 Correct 91 ms 20564 KB Output is correct
3 Correct 97 ms 20820 KB Output is correct
4 Correct 94 ms 20616 KB Output is correct
5 Correct 88 ms 20820 KB Output is correct
6 Incorrect 2 ms 10888 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 96 ms 20820 KB Output is correct
2 Correct 91 ms 20564 KB Output is correct
3 Correct 97 ms 20820 KB Output is correct
4 Correct 94 ms 20616 KB Output is correct
5 Correct 88 ms 20820 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 4 ms 11100 KB Output is correct
8 Correct 27 ms 13656 KB Output is correct
9 Correct 413 ms 37772 KB Output is correct
10 Correct 389 ms 37676 KB Output is correct
11 Correct 393 ms 37888 KB Output is correct
12 Correct 296 ms 41012 KB Output is correct
13 Correct 306 ms 41012 KB Output is correct
14 Correct 291 ms 37032 KB Output is correct

Subtask #5
0.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 20820 KB Output is correct
2 Correct 91 ms 20564 KB Output is correct
3 Correct 97 ms 20820 KB Output is correct
4 Correct 94 ms 20616 KB Output is correct
5 Correct 88 ms 20820 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 4 ms 10844 KB Output is correct
8 Correct 3 ms 10844 KB Output is correct
9 Correct 4 ms 10844 KB Output is correct
10 Correct 3 ms 10868 KB Output is correct
11 Correct 3 ms 10844 KB Output is correct
12 Correct 3 ms 10844 KB Output is correct
13 Correct 4 ms 10840 KB Output is correct
14 Correct 3 ms 10904 KB Output is correct
15 Correct 3 ms 10844 KB Output is correct
16 Incorrect 3 ms 10844 KB 63rd lines differ - on the 1st token, expected: '1386154', found: '1533190'
17 Halted 0 ms 0 KB -