Submission #924853

#TimeUsernameProblemLanguageResultExecution timeMemory
924853KarootTraffic (IOI10_traffic)C++17
0 / 100
19 ms56156 KiB
#include <traffic.h> #include <iostream> #include <cmath> #include <unordered_map> #include <map> #include <set> #include <queue> #include <vector> #include <string> #include <iomanip> #include <algorithm> #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() using namespace std; typedef long long ll; ll linf = 1e15+1; inline void scoobydoobydoo(){ ios::sync_with_stdio(false); ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } const int MAXN = 1e6+7; ll vals[MAXN]; ll subSz[MAXN]; vector<ll> adj[MAXN]; vector<ll> children[MAXN]; ll buildTree(ll node, ll parent){ subSz[node] = vals[node]; for (ll x : adj[node]){ if (x != parent){ children[node].push_back(x); subSz[node] += buildTree(x, node); } } return subSz[node]; } ll centroidFind(ll node, ll target){ for (auto& e : children[node]){ if (target < subSz[e])return centroidFind(e, target); } return node; } int LocateCentre(int N, int P[], int S[], int D[]){ for (int i = 0; i < N; i++)vals[i] = P[i]; for (int i = 0; i < N-1; i++){ adj[S[i]].push_back(D[i]); adj[D[i]].push_back(S[i]); } return centroidFind(1, buildTree(1, 1)/2); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...