#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define endl "\n"
#define elif else if
#define fo(i, a, b) for (int i = a; i < (int)b; i++)
#define rfo(i, a, b) for (int i = a - 1; i >= b; i--)
#define v(i) vector<i>
#define vll vector<long long>
#define vstr vector<string>
#define pairll pair<long long, long long>
#define vpairll vector<pair<long long, long long>>
#define print(x) cout << x << "\n"
#define pushall(x, n) \
x.resize(n); \
for (int zz = 0; zz < (int)n; zz++) \
{ \
cin >> x[zz]; \
}
vector<vector<ll>> roads;
int* fans;
ll smallestMax = LLONG_MAX;
ll smallPlace=0;
ll recur(ll on, ll prev, ll total)
{
if(roads[on].size()==1 && prev!=-1)//at the end
{
return fans[on];
}
ll maxR=-1;
ll sum=0;
for(auto x : roads[on]){
if(x != prev){
ll tmp = recur(x, on, total+fans[on]);
maxR = max(maxR, tmp);
sum+=tmp;
}
}
if(max(maxR, total) < smallestMax){
smallestMax = max(maxR, total);
smallPlace=on;
}
//should return the sum of all recurs I think, but the max should be used to find the smallestMax
return sum+fans[on];
//compare total to all the values of recur added together, looking for the smallest max
}
int LocateCentre (int num, int*p, int* s, int* d){
fans = p;
roads.resize(num);
fo(i, 0, num - 1)
{
roads[s[i]].push_back(d[i]);
roads[d[i]].push_back(s[i]);
}
ll on = 0;
while (roads[on].size() > 1)
{
on++;
} //gets the start to a point with only 1 road
if(num==1){
print(0);
return 0;
}elif(num==2){
print((fans[0] > fans[1] ? 1 : 0));
return 0;
}
recur(on, -1, 0);
return smallPlace;
}
// int main()
// {
// ios::sync_with_stdio(0);
// cin.tie(0);
// ll num;
// cin >> num;
// pushall(fans, num);
// roads.resize(num);
// fo(i, 0, num - 1)
// {
// ll n1, n2;
// cin >> n1 >> n2;
// roads[n1].push_back(n2);
// roads[n2].push_back(n1);
// }
// ll on = 0;
// while (roads[on].size() > 1)
// {
// on++;
// } //gets the start to a point with only 1 road
// if(num==1){
// print(0);
// return 0;
// }elif(num==2){
// print((fans[0] > fans[1] ? 1 : 0));
// return 0;
// }
// recur(on, -1, 0);
// print(smallPlace);
// //smallest max
// return 0;
// }
// dont want it on a city with only 1 road, its better to chose cities with a bigger population, as that doesnt add to the congestion
// in geenral, the more roads the better (as congestion is split between multiple roads)
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
