oj.uz

Submission #971563

# Submission time Handle Problem Language Result Execution time Memory
971563 2024-04-29T01:37:03 Z alo_54 Traffic (IOI10_traffic) C++14
0 / 100
 542 ms 262144 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Runtime error 542 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 542 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 542 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 542 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -