Submission #971563

#	Time	Username	Problem	Language	Result	Execution time	Memory
971563		alo_54	Traffic (IOI10_traffic)	C++14	0 / 100	542 ms	262144 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6 + 6;

int habs[MAXN];

struct Hijo
{
   int idx, resp;
};

struct newRoot
{
   int nodo, padre, respPadre;
};


vector <Hijo> ady[MAXN];

void dfs(int nodo, int padre, int idxPadre)
{
   int resp = 0;

   for (int i = 0; i < ady[nodo].size(); i++)
   {
      if (ady[nodo][i].idx != padre)
      {
         dfs(ady[nodo][i].idx, nodo, i);
         resp += ady[nodo][i].resp;
      }
      
   }

   resp += habs[nodo];

   if (padre != -1)
   {
      ady[padre][idxPadre].resp = resp;
   }
   
   
}


int LocateCentre(int N, int P[], int S[], int D[]) 
{

   for (int i = 0; i < N; i++)
   {
      habs[i] = P[i];
   }
   

   for (int i = 0; i < N-1; i++)
   {
      ady[S[i]].push_back({D[i], 0});
      ady[D[i]].push_back({S[i], 0});
   }

   //Enrizamos en 0
   //nodo, padre, indice en la lista de adyacencia de mi padre
   dfs(0, -1, -1);

   queue <newRoot> cola;

   int minW = 2e9 + 10, idxOpt = 0;

   int sum = 0;

   int hl = -1;

   for(auto i : ady[0])
   {
      sum += i.resp;

      hl = max(hl, i.resp);

   }

   minW = min(minW, hl);

   sum += P[0];

   for (auto i : ady[0])
   {
      cola.push({i.idx, 0, sum - i.resp});
   }
   

   while (!cola.empty())
   {
      newRoot curr = cola.front();
      cola.pop();

      int maxL = -1;

      for (int i = 0; i < ady[curr.nodo].size(); i++)
      {
         if (ady[curr.nodo][i].idx != curr.padre)
         {
            maxL = max(maxL, ady[curr.nodo][i].resp);
         }else
         {
            maxL = max(maxL, curr.respPadre);
         }
         
      }


      if (maxL < minW)
      {
         minW = maxL;
         idxOpt = curr.nodo;
      }
      

      sum = 0;

      for(auto i : ady[curr.nodo])
      {
         sum += i.resp;
      }

      sum += P[curr.nodo];

   
      for (auto i : ady[curr.nodo])
      {
         cola.push({i.idx, curr.nodo, sum - i.resp});
      }
   
      
   }

   return idxOpt;
 
}

Compilation message (stderr)

traffic.cpp: In function 'void dfs(int, int, int)':
traffic.cpp:27:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Hijo>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |    for (int i = 0; i < ady[nodo].size(); i++)
      |                    ~~^~~~~~~~~~~~~~~~~~
traffic.cpp: In function 'int LocateCentre(int, int*, int*, int*)':
traffic.cpp:100:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Hijo>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |       for (int i = 0; i < ady[curr.nodo].size(); i++)
      |                       ~~^~~~~~~~~~~~~~~~~~~~~~~

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