Submission #730224

#	Time	Username	Problem	Language	Result	Execution time	Memory
730224		lucri	Traffic (IOI10_traffic)	C++17	100 / 100	924 ms	149072 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
std::vector<std::vector<int>>a;
int v[1000010];
void parcurge(int nod,int ant,int pp[])
{
  for(auto x:a[nod])
  {
    if(x!=ant)
    {
      parcurge(x,nod,pp);
      v[nod]+=v[x];
    }
  }
  v[nod]+=pp[nod];
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
  if(N==1)
    return 0;
  int n=N,ans,vans=2000000000,sf,fmax,vmax,rad;
  a.resize(n+5);
  for(int i=0;i<n-1;++i)
  {
    a[S[i]].push_back(D[i]);
    a[D[i]].push_back(S[i]);
  }
  parcurge(0,-1,pp);
  ans=0;
  rad=0;
  do
  {
    sf=0;
    vmax=0;
    for(auto x:a[rad])
    {
      sf+=v[x];
      if(v[x]>vmax)
      {
        vmax=v[x];
        fmax=x;
      }
    }
    if(vmax<vans)
    {
      vans=vmax;
      ans=rad;
    }
    v[fmax]=v[rad];
    v[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:51:14: warning: 'fmax' may be used uninitialized in this function [-Wmaybe-uninitialized]
   51 |   }while(fmax!=ans);
      |          ~~~~^~~~~

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