(UPD: 2024-12-04 14:48 UTC) Judge is not working due to Cloudflare incident. (URL) We can do nothing about it, sorry. After the incident is resolved, we will grade all submissions.

Submission #394756

#TimeUsernameProblemLanguageResultExecution timeMemory
394756MarcoMeijerTraffic (IOI10_traffic)C++14
100 / 100
1485 ms186364 KiB
#include "traffic.h" #include <bits/stdc++.h> using namespace std; // macros typedef long long ll; typedef long double ld; typedef pair<int, int> ii; typedef pair<ll, ll> lll; typedef tuple<int, int, int> iii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<iii> viii; typedef vector<ll> vll; typedef vector<lll> vlll; #define REP(a,b,c) for(int a=int(b); a<int(c); a++) #define RE(a,c) REP(a,0,c) #define RE1(a,c) REP(a,1,c+1) #define REI(a,b,c) REP(a,b,c+1) #define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--) #define FOR(a,b) for(auto& a : b) #define all(a) a.begin(), a.end() #define INF (2e9+1) #define EPS 1e-9 #define pb push_back #define popb pop_back #define fi first #define se second int LocateCentre(int N, int pp[], int S[], int D[]) { vector<vi> adj; adj.resize(N); vi sz; sz.assign(N,0); vi par; par.assign(N,-1); // fill adj RE(i,N-1) adj[S[i]].pb(D[i]); RE(i,N-1) adj[D[i]].pb(S[i]); function<void(int,int)> fillSize = [&](int u, int p) { sz[u] = pp[u]; par[u] = p; FOR(v,adj[u]) { if(v == p) continue; fillSize(v,u); sz[u] += sz[v]; } }; function<int(int)> getCost = [&](int u) { int res = sz[0] - sz[u]; FOR(v,adj[u]) { if(v == par[u]) continue; res = max(res, sz[v]); } return res; }; fillSize(0,-1); int bst = 0, bstCost = getCost(0); RE(i,N) if(getCost(i) < bstCost) { bstCost = getCost(i); bst = i; } return bst; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...