Submission #1092149

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092149		TlenekWodoru	Truck Driver (IOI23_deliveries)	C++17	100 / 100	1006 ms	89124 KiB

deliveries

#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 / 8
• Subtask 2: 21 / 21
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 36 / 36