Submission #831555

#TimeUsernameProblemLanguageResultExecution timeMemory
831555otariusTraffic (IOI10_traffic)C++17
100 / 100
955 ms170676 KiB
#include "traffic.h" #include <iostream> #include <algorithm> #include <vector> #include <set> #include <cstring> #include <queue> #include <map> #include <cmath> #include <iomanip> using namespace std; #define ff first #define sc second #define pb push_back #define ll long long #define pll pair<ll, ll> #define pii pair <int, int> #define ull unsigned long long // #define int long long // #define int unsigned long long const ll inf = 1e18 + 7; const ll weirdMod = 998244353; int x, y; vector<int> G[1000005]; ll sum[1000005], mn = inf, ans; void dfs(int v, int par) { for (int u : G[v]) { if (u != par) { dfs(u, v); sum[v] += sum[u]; } } } void solve(int v, int par) { ll mx = sum[0] - sum[v]; for (int u : G[v]) { if (u != par) { mx = max(mx, sum[u]); solve(u, v); } } if (mx < mn) { mn = mx; ans = v; } } int LocateCentre(int n, int p[], int s[], int d[]) { for (int i = 0; i < n; i++) sum[i] = p[i]; for (int i = 0; i < n - 1; i++) { G[s[i]].pb(d[i]); G[d[i]].pb(s[i]); } dfs(0, -1); solve(0, -1); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...