Submission #730214

#	Time	Username	Problem	Language	Result	Execution time	Memory
730214		lucri	Traffic (IOI10_traffic)	C++17	0 / 100	5050 ms	23916 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
std::vector<long long>a[1000010];
long long nr[1000010];
void parcurge(long long nod,long long ant)
{
    for(auto x:a[nod])
    {
        if(x!=ant)
        {
            parcurge(x,nod);
            nr[nod]+=nr[x];
        }
    }
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
    long long n=N,ans,vans=2000000000,sf,fmax,vmax,rad;
    for(long long i=0;i<n-1;++i)
    {
        nr[i]=pp[i];
        a[S[i]].push_back(D[i]);
        a[D[i]].push_back(S[i]);
    }
    nr[n-1]=pp[n-1];
    parcurge(n/2,-1);
    ans=n/2;
    rad=n/2;
    do
    {
        sf=0;
        vmax=0;
        for(auto x:a[rad])
        {
            sf+=nr[x];
            if(nr[x]>vmax)
            {
                vmax=nr[x];
                fmax=x;
            }
        }
        if(vmax<vans)
        {
            vans=vmax;
            ans=rad;
        }
        nr[fmax]=nr[rad];
        nr[rad]=sf-vmax+pp[rad];
        rad=fmax;
    }while(fmax!=ans);
    for(long long i=1;i<=n;++i)
    {
        a[i].clear();
    }
    return ans;
}

Compilation message (stderr)

traffic.cpp: In function 'int LocateCentre(int, int*, int*, int*)':
traffic.cpp:49:16: warning: 'fmax' may be used uninitialized in this function [-Wmaybe-uninitialized]
   49 |     }while(fmax!=ans);
      |            ~~~~^~~~~

• Subtask 1: 0 / 25
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25