Submission #972003

#	Time	Username	Problem	Language	Result	Execution time	Memory
972003		alo_54	Traffic (IOI10_traffic)	C++14	100 / 100	919 ms	170740 KiB

traffic

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

using namespace std;

const int MAXN = 1e6 + 6;
int habs[MAXN];
int respNodo[MAXN];


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

vector <int> ady[MAXN];


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

   for(auto i : ady[nodo])
   {
     if (i != padre)
     {
        dfs(i, nodo);
        resp += respNodo[i];
     }
   }

   resp += habs[nodo];

   respNodo[nodo] = 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]);
      ady[D[i]].push_back(S[i]);
   }

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

   queue <newRoot> cola;

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

   int sum = 0;

   int hl = -1;

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

      hl = max(hl, respNodo[i]);
   }

   sum += P[0];

   minW = min(minW, hl);

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

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

      int maxL = -1, sum = 0;

      for(auto i : ady[curr.nodo])
      {
        if (i != curr.padre)
        {
            maxL = max(maxL, respNodo[i]);
            sum += respNodo[i];
        }else
        {
            maxL = max(maxL, curr.respPadre);
            sum += curr.respPadre;
        }
      }

      sum += P[curr.nodo];


      if (maxL < minW)
      {
         minW = maxL;
         idxOpt = curr.nodo;
      }
      
   
      for (auto i : ady[curr.nodo])
      {
        if (i != curr.padre)
        {
            cola.push({i, curr.nodo, sum - respNodo[i]});
        }
        
      }
   
   }

   return idxOpt;

   //cout<<idxOpt<<endl;
 
}

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