oj.uz

답안 #1092148

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1092148 2024-09-23T10:24:51 Z TlenekWodoru Truck Driver (IOI23_deliveries) C++17
43 / 100
 769 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-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<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

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 33872 KB Output is correct
2 Correct 79 ms 33704 KB Output is correct
3 Correct 73 ms 33952 KB Output is correct
4 Correct 72 ms 33940 KB Output is correct
5 Correct 74 ms 33872 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 23900 KB Output is correct
2 Correct 13 ms 24376 KB Output is correct
3 Correct 12 ms 24156 KB Output is correct
4 Correct 12 ms 24284 KB Output is correct
5 Correct 14 ms 24408 KB Output is correct
6 Correct 13 ms 24408 KB Output is correct
7 Correct 12 ms 24412 KB Output is correct
8 Correct 11 ms 24300 KB Output is correct
9 Correct 13 ms 24364 KB Output is correct
10 Correct 12 ms 24668 KB Output is correct
11 Correct 11 ms 24156 KB Output is correct
12 Correct 12 ms 24236 KB Output is correct
13 Correct 12 ms 24208 KB Output is correct
14 Correct 13 ms 24412 KB Output is correct
15 Correct 12 ms 24412 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 33872 KB Output is correct
2 Correct 79 ms 33704 KB Output is correct
3 Correct 73 ms 33952 KB Output is correct
4 Correct 72 ms 33940 KB Output is correct
5 Correct 74 ms 33872 KB Output is correct
6 Correct 12 ms 23900 KB Output is correct
7 Correct 13 ms 24412 KB Output is correct
8 Correct 44 ms 28384 KB Output is correct
9 Correct 559 ms 68844 KB Output is correct
10 Correct 550 ms 68948 KB Output is correct
11 Correct 517 ms 69136 KB Output is correct
12 Correct 287 ms 71468 KB Output is correct
13 Correct 285 ms 71728 KB Output is correct
14 Correct 300 ms 71468 KB Output is correct

Subtask #4
0.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 33872 KB Output is correct
2 Correct 79 ms 33704 KB Output is correct
3 Correct 73 ms 33952 KB Output is correct
4 Correct 72 ms 33940 KB Output is correct
5 Correct 74 ms 33872 KB Output is correct
6 Correct 12 ms 23896 KB Output is correct
7 Correct 14 ms 24464 KB Output is correct
8 Correct 50 ms 30088 KB Output is correct
9 Correct 731 ms 85988 KB Output is correct
10 Correct 730 ms 86000 KB Output is correct
11 Correct 769 ms 86064 KB Output is correct
12 Incorrect 305 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

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 33872 KB Output is correct
2 Correct 79 ms 33704 KB Output is correct
3 Correct 73 ms 33952 KB Output is correct
4 Correct 72 ms 33940 KB Output is correct
5 Correct 74 ms 33872 KB Output is correct
6 Correct 11 ms 23900 KB Output is correct
7 Correct 13 ms 24376 KB Output is correct
8 Correct 12 ms 24156 KB Output is correct
9 Correct 12 ms 24284 KB Output is correct
10 Correct 14 ms 24408 KB Output is correct
11 Correct 13 ms 24408 KB Output is correct
12 Correct 12 ms 24412 KB Output is correct
13 Correct 11 ms 24300 KB Output is correct
14 Correct 13 ms 24364 KB Output is correct
15 Correct 12 ms 24668 KB Output is correct
16 Correct 11 ms 24156 KB Output is correct
17 Correct 12 ms 24236 KB Output is correct
18 Correct 12 ms 24208 KB Output is correct
19 Correct 13 ms 24412 KB Output is correct
20 Correct 12 ms 24412 KB Output is correct
21 Correct 12 ms 23900 KB Output is correct
22 Correct 13 ms 24412 KB Output is correct
23 Correct 44 ms 28384 KB Output is correct
24 Correct 559 ms 68844 KB Output is correct
25 Correct 550 ms 68948 KB Output is correct
26 Correct 517 ms 69136 KB Output is correct
27 Correct 287 ms 71468 KB Output is correct
28 Correct 285 ms 71728 KB Output is correct
29 Correct 300 ms 71468 KB Output is correct
30 Correct 12 ms 23896 KB Output is correct
31 Correct 14 ms 24464 KB Output is correct
32 Correct 50 ms 30088 KB Output is correct
33 Correct 731 ms 85988 KB Output is correct
34 Correct 730 ms 86000 KB Output is correct
35 Correct 769 ms 86064 KB Output is correct
36 Incorrect 305 ms 89136 KB 3rd lines differ - on the 1st token, expected: '125599030041442104', found: '125599293915363628'
37 Halted 0 ms 0 KB -