Submission #1068289

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068289		TlenekWodoru	Truck Driver (IOI23_deliveries)	C++17	29 / 100	5595 ms	20268 KiB

deliveries

#include<bits/stdc++.h>
#include "deliveries.h"
using namespace std;
struct Edge
{
    int b,c;
};
vector<Edge>D[100009];
int Deliv[100009];
long long NadMna[100009];
long long NadSuma[100009];
long long Suma[100009];
bool CzyGit[100009];
int n;
void DFS(int v, int last)
{
    NadMna[v]=Deliv[v];
    NadSuma[v]=0;
    for(auto[som,o] : D[v])
    {
        if(som==last){continue;}
        DFS(som,v);
        NadMna[v]+=NadMna[som];
        NadSuma[v]+=NadMna[som]*o+NadSuma[som];
    }
}
void DFS2(int v, int last)
{
    long long maxx=0;
    for(auto[som,o] : D[v])
    {
        if(som==last){continue;}
        Suma[som]=Suma[v]+(NadMna[0]-NadMna[som])*o-NadMna[som]*o;
        maxx=max(maxx,NadMna[som]);
        DFS2(som,v);
    }
    maxx=max(maxx,NadMna[0]-NadMna[v]);
    int odj=0;
    if(v==0){odj=1;}
    if(maxx*2>NadMna[0]-odj){CzyGit[v]=0;}
    else{CzyGit[v]=1;}
}
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++)
    {
        int a=AA[i];
        int b=BB[i];
        int c=CC[i];
        D[a].push_back({b,c});
        D[b].push_back({a,c});
    }
    for(int i=0;i<n;i++)
    {
        Deliv[i]=W[i];
    }
    Deliv[0]++;
	return;
}

long long max_time(int v, int x)
{
    if(v==0){x++;}
    Deliv[v]=x;
    DFS(0,-1);
    Suma[0]=NadSuma[0];
    DFS2(0,-1);
    long long wyn=0;
    for(int i=0;i<n;i++)
    {
        if(CzyGit[i]==0){continue;}
        wyn=max(wyn,Suma[i]*2);
    }
	return wyn;
}

• Subtask 1: 8 / 8
• Subtask 2: 21 / 21
• Subtask 3: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 36