oj.uz

Submission #1092132

# Submission time Handle Problem Language Result Execution time Memory
1092132 2024-09-23T09:29:51 Z TlenekWodoru Truck Driver (IOI23_deliveries) C++17
22 / 100
 843 ms 89136 KB 
#include<bits/stdc++.h>
#include "deliveries.h"
using namespace std;
struct Edge
{
    int som,o;
};
vector<Edge>D[200009];
vector<int>G[200009],Skad[200009];
bool zaj[200009];
long long Suma[200009],Ile[200009];
vector<long long>Suma2[200009],Ile2[200009];
long long Odl[20][200009];
int NadMna[200009],Deep[200009],Last[200009],Numer[200009];
int tab[200009];
int Gl[200009],Gp[200009],GLast[200009];
long long Tre[1000000];
int n,centr,base,start,h;
long long s=0;
long long Przedzial(int l, int p)
{
    l+=base;
    p+=base;
    long long wyn=0;
    while(l<=p)
    {
        if(l%2==1)
        {
            wyn+=Tre[l];
            l++;
        }
        if(p%2==0)
        {
            wyn+=Tre[p];
            p--;
        }
        l>>=1;
        p>>=1;
    }
    return wyn;
}
void Punkt(int v, int dod)
{
    v+=base;
    while(v>0)
    {
        Tre[v]+=dod;
        v>>=1;
    }
}
int TworzenieDrzewa(int x)
{
    x--;
    int u=1;
    while(x>0)
    {
        x>>=1;
        u<<=1;
    }
    return u;
}
long long IleNad(int a, int b)
{
    if(b==GLast[a])
    {
        return s-Przedzial(Gl[a],Gp[a]);
    }
    else
    {
        return Przedzial(Gl[b],Gp[b]);
    }
}
void GDFS(int v, int last)
{
    GLast[v]=last;
    for(auto[som,o] : D[v])
    {
        if(som==last){continue;}
        GDFS(som,v);
    }
    Gl[v]=h;
    Gp[v]=h;
    h--;
    for(auto[som,o] : D[v])
    {
        if(som==last){continue;}
        Gp[v]=max(Gp[v],Gp[som]);
    }
}
void CentrDod(int v, int dod)
{
    Punkt(Gl[v],dod);
    s+=dod;
    Ile[v]+=dod;
    int u=v;
    while(Last[u]!=-1)
    {
        int num=Numer[u];
        u=Last[u];
        Suma[u]+=Odl[Deep[u]][v]*dod;
        Ile[u]+=dod;
        Suma2[u][num]+=Odl[Deep[u]][v]*dod;
        Ile2[u][num]+=dod;
    }
}
long long CentrOblicz(int v)
{
    long long wynik=Suma[v];
    int u=v;
    while(Last[u]!=-1)
    {
        int num=Numer[u];
        u=Last[u];
        wynik+=Suma[u]-Suma2[u][num];
        wynik+=(Ile[u]-Ile2[u][num])*Odl[Deep[u]][v];
    }
    return wynik;
}
void DFSCentr(int v, int last,const int &r)
{
    NadMna[v]=1;
    bool cv=1;
    for(auto[som,o] : D[v])
    {
        if(som==last||zaj[som]){continue;}
        DFSCentr(som,v,r);
        NadMna[v]+=NadMna[som];
        if(NadMna[som]>(r>>1)){cv=0;}
    }
    if(r-NadMna[v]>(r>>1)){cv=0;}
    if(cv){centr=v;}
}
void DFSOdl(int v, int deep, long long odl, int last)
{
    Odl[deep][v]=odl;
    for(auto[som,o] : D[v])
    {
        if(som==last||zaj[som]){continue;}
        DFSOdl(som,deep,odl+o,v);
    }
}
void CENTROID(int v, int r, int deep, int last, int numer)
{
    DFSCentr(v,-1,r);
    if(last!=-1)
    {
        G[last].push_back(centr);
        Skad[last].push_back(v);
    }
    v=centr;
    Deep[v]=deep;
    Last[v]=last;
    Numer[v]=numer;
    Suma2[v].resize(D[v].size());
    Ile2[v].resize(D[v].size());
    DFSOdl(v,deep,0,-1);
    DFSCentr(v,-1,0);
    zaj[v]=1;
    for(int i=0;i<(int)D[v].size();i++)
    {
        const int som=D[v][i].som;
        if(zaj[som]){continue;}
        CENTROID(som,NadMna[som],deep+1,v,i);
    }
    zaj[v]=0;
}
void F(int v, vector<Edge>U)
{
    if(U.size()==0){return;}
    if(U.size()<=2)
    {
        for(Edge e : U)
        {
            D[v].push_back(e);
            D[e.som].push_back({v,e.o});
        }
        return;
    }
    vector<Edge>A,B;
    while(U.size()>0)
    {
        if(A.size()<=B.size()){A.push_back(U.back());}
        else{B.push_back(U.back());}
        U.pop_back();
    }
    n++;
    const int u=n;
    D[v].push_back({u,0});
    D[u].push_back({v,0});
    F(u,A);
    F(u,B);
}
void DFS(int v, int last)
{
    vector<Edge>U;
    for(int i=0;i<(int)D[v].size();i++)
    {
        const int som=D[v][i].som;
        if(som==last){continue;}
        U.push_back(D[v][i]);
        DFS(som,v);
    }
    D[v].clear();
    F(v,U);
}
long long GetWynik()
{
    int v=start;
    while(true)
    {
        pair<int,int>maxx={0,0};
        for(int i=0;i<(int)G[v].size();i++)
        {
            maxx=max(maxx,{IleNad(v,Skad[v][i]),G[v][i]});
        }
        if(maxx.first>(s>>1)){v=maxx.second;}
        else
        {
            return CentrOblicz(v)*2;
        }
    }
}
void init(int N, vector<int>AA, vector<int>BB, vector<int>CC, vector<int>W)
{
    n=N;
    for(int i=0;i<n-1;i++)
    {
        D[AA[i]].push_back({BB[i],CC[i]});
        D[BB[i]].push_back({AA[i],CC[i]});
    }
    DFS(0,-1);
    base=TworzenieDrzewa(n);
    h=n;
    GDFS(0,-1);
    CENTROID(0,n,0,-1,-1);
    for(int i=0;i<n;i++)
    {
        if(Deep[i]==0)
        {
            start=i;
            break;
        }
    }
    W[0]++;
    for(int i=0;i<(int)W.size();i++)
    {
        CentrDod(i,W[i]);
        tab[i]=W[i];
    }
}
long long max_time(int v, int x)
{
    if(v==0){x++;}
    int dod=x-tab[v];
    tab[v]=x;
    CentrDod(v,dod);
    return GetWynik();
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 33872 KB Output is correct
2 Correct 69 ms 33620 KB Output is correct
3 Correct 70 ms 33952 KB Output is correct
4 Correct 69 ms 33872 KB Output is correct
5 Correct 91 ms 33824 KB Output is correct

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Incorrect 11 ms 24296 KB 3rd lines differ - on the 1st token, expected: '10221304', found: '7373024'
3 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 33872 KB Output is correct
2 Correct 69 ms 33620 KB Output is correct
3 Correct 70 ms 33952 KB Output is correct
4 Correct 69 ms 33872 KB Output is correct
5 Correct 91 ms 33824 KB Output is correct
6 Correct 10 ms 23900 KB Output is correct
7 Correct 12 ms 24348 KB Output is correct
8 Correct 41 ms 28396 KB Output is correct
9 Correct 536 ms 68920 KB Output is correct
10 Correct 559 ms 69108 KB Output is correct
11 Correct 533 ms 68836 KB Output is correct
12 Correct 300 ms 71424 KB Output is correct
13 Correct 314 ms 71476 KB Output is correct
14 Correct 291 ms 71540 KB Output is correct

Subtask #4
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 33872 KB Output is correct
2 Correct 69 ms 33620 KB Output is correct
3 Correct 70 ms 33952 KB Output is correct
4 Correct 69 ms 33872 KB Output is correct
5 Correct 91 ms 33824 KB Output is correct
6 Correct 11 ms 24152 KB Output is correct
7 Correct 13 ms 24368 KB Output is correct
8 Correct 51 ms 30032 KB Output is correct
9 Correct 822 ms 86124 KB Output is correct
10 Correct 843 ms 86032 KB Output is correct
11 Correct 835 ms 86076 KB Output is correct
12 Incorrect 302 ms 89136 KB 3rd lines differ - on the 1st token, expected: '125599030041442104', found: '125599293915363628'
13 Halted 0 ms 0 KB -

Subtask #5
0.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 33872 KB Output is correct
2 Correct 69 ms 33620 KB Output is correct
3 Correct 70 ms 33952 KB Output is correct
4 Correct 69 ms 33872 KB Output is correct
5 Correct 91 ms 33824 KB Output is correct
6 Correct 10 ms 23900 KB Output is correct
7 Incorrect 11 ms 24296 KB 3rd lines differ - on the 1st token, expected: '10221304', found: '7373024'
8 Halted 0 ms 0 KB -