# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
971563 |
2024-04-29T01:37:03 Z |
alo_54 |
Traffic (IOI10_traffic) |
C++14 |
|
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++)
| ~~^~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
542 ms |
262144 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
542 ms |
262144 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
542 ms |
262144 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
542 ms |
262144 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |