#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define fst first
#define snd second
const int MAXN = 1000005;
ll sum = 0, down[MAXN], maxim[MAXN];
vi Graph[MAXN];
void dfs(int node, int p = -1)
{
sum += node;
down[node] = node;
for(auto i : Graph[node])
if(i != p)
{
dfs(i, node);
down[node] += down[i];
maxim[node] = max(maxim[node], down[i]);
}
}
int LocateCentre(int N, int P[], int S[], int D[])
{
sum = 0;
for(int i = 0; i < N; i++)
{
Graph[i].clear();
down[i] = 0;
maxim[i] = 0;
}
for(int i = 0; i < N - 1; i++)
Graph[S[i]].pb(D[i]);
dfs(0);
int ans = 0;
ll minim = (1LL << 60LL);
for(int i = 0; i < N; i++)
if(max(maxim[i], sum - down[i]) < minim)
{
minim = max(maxim[i], sum - down[i]);
ans = i;
}
return ans;
}
/*
int main ()
{
int n;
cin >> n;
int p[n];
for(int i = 0; i < n; i++)
cin >> p[i];
int u[n - 1], v[n - 1];
for(int i = 0; i < n - 1; i++)
cin >> u[i] >> v[i];
cout << LocateCentre(n, p, u, v) << "\n";
return 0;
}
*/
/*
- if use ceil/floor, cast to int.
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
23808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
23808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
23808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
23808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
