Submission #730212

#	Time	Username	Problem	Language	Result	Execution time	Memory
730212		lucri	Traffic (IOI10_traffic)	C++17	0 / 100	1 ms	340 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
long long nr[1000010];
void parcurge(long long nod,long long ant,std::vector<std::vector<long long>>&a)
{
    for(auto x:a[nod])
    {
        if(x!=ant)
        {
            parcurge(x,nod,a);
            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;
	std::vector<std::vector<long long>>a;
  	a.resize(n+5);
    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,a);
    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);
    return ans;
}

Compilation message (stderr)

traffic.cpp: In function 'int LocateCentre(int, int*, int*, int*)':
traffic.cpp:47:17: warning: 'fmax' may be used uninitialized in this function [-Wmaybe-uninitialized]
   47 |         nr[fmax]=nr[rad];
      |         ~~~~~~~~^~~~~~~~

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