Submission #730186

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

traffic

    #include "traffic.h"
    #include <bits/stdc++.h>
    std::vector<std::vector<int>>a;
    int nr[1000010];
    void parcurge(int nod,int 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[]) {
        int n=N,ans,vans=2000000000,sf,fmax,vmax,rad;
        a.resize(n+5);
        for(int 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);
        return ans;
    }

Compilation message (stderr)

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

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