oj.uz

Submission #1092149

# Submission time Handle Problem Language Result Execution time Memory
1092149 2024-09-23T10:29:58 Z TlenekWodoru Truck Driver (IOI23_deliveries) C++17
100 / 100
 1006 ms 89124 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-1;
    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<long long,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 75 ms 33872 KB Output is correct
2 Correct 81 ms 33620 KB Output is correct
3 Correct 79 ms 33948 KB Output is correct
4 Correct 76 ms 33804 KB Output is correct
5 Correct 77 ms 33876 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23900 KB Output is correct
2 Correct 12 ms 24152 KB Output is correct
3 Correct 12 ms 24156 KB Output is correct
4 Correct 13 ms 24336 KB Output is correct
5 Correct 14 ms 24412 KB Output is correct
6 Correct 14 ms 24508 KB Output is correct
7 Correct 12 ms 24408 KB Output is correct
8 Correct 13 ms 24412 KB Output is correct
9 Correct 12 ms 24408 KB Output is correct
10 Correct 12 ms 24408 KB Output is correct
11 Correct 12 ms 24152 KB Output is correct
12 Correct 12 ms 24412 KB Output is correct
13 Correct 13 ms 24412 KB Output is correct
14 Correct 12 ms 24416 KB Output is correct
15 Correct 13 ms 24412 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 33872 KB Output is correct
2 Correct 81 ms 33620 KB Output is correct
3 Correct 79 ms 33948 KB Output is correct
4 Correct 76 ms 33804 KB Output is correct
5 Correct 77 ms 33876 KB Output is correct
6 Correct 11 ms 23900 KB Output is correct
7 Correct 12 ms 24412 KB Output is correct
8 Correct 41 ms 28408 KB Output is correct
9 Correct 519 ms 68844 KB Output is correct
10 Correct 517 ms 68908 KB Output is correct
11 Correct 501 ms 68904 KB Output is correct
12 Correct 310 ms 71112 KB Output is correct
13 Correct 288 ms 71120 KB Output is correct
14 Correct 289 ms 71056 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 33872 KB Output is correct
2 Correct 81 ms 33620 KB Output is correct
3 Correct 79 ms 33948 KB Output is correct
4 Correct 76 ms 33804 KB Output is correct
5 Correct 77 ms 33876 KB Output is correct
6 Correct 11 ms 23896 KB Output is correct
7 Correct 12 ms 24412 KB Output is correct
8 Correct 51 ms 30004 KB Output is correct
9 Correct 786 ms 85812 KB Output is correct
10 Correct 791 ms 85808 KB Output is correct
11 Correct 781 ms 85804 KB Output is correct
12 Correct 577 ms 88620 KB Output is correct
13 Correct 570 ms 89124 KB Output is correct
14 Correct 393 ms 85212 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 33872 KB Output is correct
2 Correct 81 ms 33620 KB Output is correct
3 Correct 79 ms 33948 KB Output is correct
4 Correct 76 ms 33804 KB Output is correct
5 Correct 77 ms 33876 KB Output is correct
6 Correct 11 ms 23900 KB Output is correct
7 Correct 12 ms 24152 KB Output is correct
8 Correct 12 ms 24156 KB Output is correct
9 Correct 13 ms 24336 KB Output is correct
10 Correct 14 ms 24412 KB Output is correct
11 Correct 14 ms 24508 KB Output is correct
12 Correct 12 ms 24408 KB Output is correct
13 Correct 13 ms 24412 KB Output is correct
14 Correct 12 ms 24408 KB Output is correct
15 Correct 12 ms 24408 KB Output is correct
16 Correct 12 ms 24152 KB Output is correct
17 Correct 12 ms 24412 KB Output is correct
18 Correct 13 ms 24412 KB Output is correct
19 Correct 12 ms 24416 KB Output is correct
20 Correct 13 ms 24412 KB Output is correct
21 Correct 11 ms 23900 KB Output is correct
22 Correct 12 ms 24412 KB Output is correct
23 Correct 41 ms 28408 KB Output is correct
24 Correct 519 ms 68844 KB Output is correct
25 Correct 517 ms 68908 KB Output is correct
26 Correct 501 ms 68904 KB Output is correct
27 Correct 310 ms 71112 KB Output is correct
28 Correct 288 ms 71120 KB Output is correct
29 Correct 289 ms 71056 KB Output is correct
30 Correct 11 ms 23896 KB Output is correct
31 Correct 12 ms 24412 KB Output is correct
32 Correct 51 ms 30004 KB Output is correct
33 Correct 786 ms 85812 KB Output is correct
34 Correct 791 ms 85808 KB Output is correct
35 Correct 781 ms 85804 KB Output is correct
36 Correct 577 ms 88620 KB Output is correct
37 Correct 570 ms 89124 KB Output is correct
38 Correct 393 ms 85212 KB Output is correct
39 Correct 12 ms 23896 KB Output is correct
40 Correct 19 ms 24412 KB Output is correct
41 Correct 66 ms 29780 KB Output is correct
42 Correct 1006 ms 81176 KB Output is correct
43 Correct 940 ms 81820 KB Output is correct
44 Correct 896 ms 82616 KB Output is correct
45 Correct 879 ms 83516 KB Output is correct
46 Correct 842 ms 84632 KB Output is correct
47 Correct 673 ms 83580 KB Output is correct
48 Correct 646 ms 84244 KB Output is correct
49 Correct 639 ms 84784 KB Output is correct
50 Correct 606 ms 85672 KB Output is correct
51 Correct 593 ms 86840 KB Output is correct
52 Correct 462 ms 77612 KB Output is correct
53 Correct 383 ms 77436 KB Output is correct
54 Correct 398 ms 77872 KB Output is correct
55 Correct 519 ms 83252 KB Output is correct
56 Correct 529 ms 84220 KB Output is correct
57 Correct 550 ms 83928 KB Output is correct