#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
int pct(int x) { return __builtin_popcount(x); }
// TO_STRING, credits: Benq
#define ts to_string
string ts(char c) { return string(1,c); }
string ts(bool b) { return b ? "true" : "false"; }
string ts(const char* s) { return (string)s; }
string ts(string s) { return s; }
template<class A> string ts(complex<A> c) {
stringstream ss; ss << c; return ss.str(); }
string ts(vector<bool> v) {
string res = "{"; for(int i = 0; i < sz(v); i++) res += char('0'+v[i]);
res += "}"; return res; }
template<size_t SZ> string ts(bitset<SZ> b) {
string res = ""; for(int i = 0; i < SZ; i++) res += char('0'+b[i]);
return res; }
template<class A, class B> string ts(pair<A,B> p);
template<class T> string ts(T v) { // containers with begin(), end()
bool fst = 1; string res = "{";
for (const auto& x: v) {
if (!fst) res += ", ";
fst = 0; res += ts(x);
}
res += "}"; return res;
}
template<class A, class B> string ts(pair<A,B> p) {
return "("+ts(p.first)+", "+ts(p.second)+")"; }
// DEBUG, credits: Benq
void DBG() {
cerr << "]" << endl;
}
template<class H, class... T> void DBG(H h, T... t) {
cerr << ts(h);
if (sizeof...(t))
cerr << ", ";
DBG(t...);
}
#ifdef LOCAL // compile with -DLOCAL
#define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#define optimizeIO() 0
#define openFiles() 0
#else
#define dbg(...) 0
#define optimizeIO() ios_base::sync_with_stdio(0); cin.tie(0)
#define openFiles() freopen("file.in", "r", stdin); freopen("file.out", "w", stdout)
#endif
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[])
{
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 ()
{
optimizeIO();
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.
*/
Compilation message
traffic.cpp: In function 'void DBG(H, T ...)':
traffic.cpp:54:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
54 | if (sizeof...(t))
| ^~
traffic.cpp:56:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
56 | DBG(t...);
| ^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
16 ms |
23808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
16 ms |
23808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
16 ms |
23808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
16 ms |
23808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
