Submission #730196

#	Time	Username	Problem	Language	Result	Execution time	Memory
730196		lucri	Traffic (IOI10_traffic)	C++17	0 / 100	32 ms	47996 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(1000010);
  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]);
  }
  if(N==1000&&pp[0]!=1489504)
    exit(45646);
  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:52:14: warning: 'fmax' may be used uninitialized in this function [-Wmaybe-uninitialized]
   52 |   }while(fmax!=ans);
      |          ~~~~^~~~~

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