Submission #429877

#TimeUsernameProblemLanguageResultExecution timeMemory
429877OdaveyRace (IOI11_race)C++14
21 / 100
3097 ms137524 KiB
// // ~oisín~ C++ Template // #include <bits/stdc++.h> #define MX_N 200005 #define mp make_pair #define mod7 1000000007 #define modpi 314159 #define PI 3.141592653589793238 #define pb push_back #define FastIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define All(a) a.begin(),a.end() #define fi first #define se second #define ll long long int #define ull unsigned long long int int kx[8] = {+2, +2, -2, -2, +1, +1, -1, -1}; int ky[8] = {+1, -1, +1, -1, +2, -2, +2, -2}; int d9x[9] = {+1, +1, +1, +0, +0, +0, -1, -1, -1}; int d9y[9] = {+1, +0, -1, +1, +0, -1, +1, +0, -1}; int dx4[4] = {+0, +0, +1, -1}; int dy4[4] = {+1, -1, +0, +0}; ll gcd(ull a, ull b){ return (a==0)?b:gcd(b%a,a); } ll lcm(ull a, ull b){ return a*(b/gcd(a,b)); } const long long INF = 1e18; using namespace std; map<ll, bool> d_b; map<ll, int> d_id; map<int, int> l_q[MX_N]; ll k; bool is_heavy[MX_N]; int card[MX_N], p[MX_N], heavy[MX_N], l[MX_N], tin[MX_N], tout[MX_N], whom[MX_N*2]; ll depth[MX_N]; int gl_tit = 0; int gl_dit = 0; vector<pair<int, ll> > adj[MX_N]; void info_dfs(int at){ whom[gl_tit] = at; tin[at] = gl_tit++; card[at] = 1; for(auto& [to, w] : adj[at]){ if(p[at] == to){ continue; } p[to] = at; l[to] = l[at] + 1; depth[to] = depth[at] + w; info_dfs(to); //card[at] += card[to]; if(heavy[at] == -1){ heavy[at] = to; }else{ if(card[to] > card[heavy[at]]){ heavy[at] = to; } } } if(heavy[at] != -1){ is_heavy[heavy[at]] = true; } whom[gl_tit] = -1; tout[at] = gl_tit++; return; } int ans = 1000000009; void dfs(int at){ for(auto& [to, w] : adj[at]){ if(to == p[at] || is_heavy[to]){ continue; } dfs(to); } if(heavy[at] != -1){ dfs(heavy[at]); } for(auto& [to, w] : adj[at]){ if(to == p[at] || is_heavy[to]){ continue; } for(int i=tin[to];i<=tout[to];++i){ if(whom[i] == -1){ continue; } if(d_b[depth[whom[i]]] == false){ l_q[gl_dit][l[whom[i]]]++; d_id[depth[whom[i]]] = gl_dit++; d_b[depth[whom[i]]] = true; }else{ int tmp_it = d_id[depth[whom[i]]]; l_q[tmp_it][l[whom[i]]]++; } } } if(d_b[depth[at]] == false){ l_q[gl_dit][l[at]]++; d_id[depth[at]] = gl_dit++; d_b[depth[at]] = true; }else{ int tmp_it = d_id[depth[at]]; l_q[tmp_it][l[at]]++; } for(auto& [to, w] : adj[at]){ if(to == p[at] || is_heavy[to]){ continue; } for(int i=tin[to];i<=tout[to];++i){ if(whom[i] == -1){ continue; } int a = whom[i]; ll db = k + 2ll*depth[at] - depth[a]; if(d_b[db] == false){ continue; } int tmp_id = d_id[db]; if(l_q[tmp_id].empty()){ continue; } int lb = l_q[tmp_id].begin()->first; if(((lb == l[a]) && (l_q[tmp_id][lb] == 1) && depth[a] == db) || (l_q[tmp_id][lb] == 0)){ continue; } ans = min(ans, l[a] + lb - 2*l[at]); } } int a = at; int tmp_id, lb; ll db = k + 2ll*depth[at] - depth[a]; if(d_b[db] == false){ goto crime; } tmp_id = d_id[db]; if(l_q[tmp_id].empty()){ goto crime; } lb = l_q[tmp_id].begin()->first; if(((lb == l[a]) && (l_q[tmp_id][lb] == 1) && depth[a] == db) || (l_q[tmp_id][lb] == 0)){ goto crime; } ans = min(ans, l[a] + lb - 2*l[at]); crime: if(!is_heavy[at]){ for(int i=tin[at];i<=tout[at];++i){ if(whom[i] == -1){ continue; } int tmp_it = d_id[depth[whom[i]]]; l_q[tmp_it][l[whom[i]]]--; if(l_q[tmp_it][l[whom[i]]] == 0){ l_q[tmp_it].erase(whom[i]); } } } return; } int best_path(int N, int K, int H[][2], int L[]){ for(int i=0;i<N-1;++i){ int u = H[i][0], v = H[i][1]; ll w = L[i]; adj[u].pb({v, w}); adj[v].pb({u, w}); l_q[i].clear(); } gl_tit = 0; gl_dit = 0; l_q[N-1].clear(); d_id.clear(); d_b.clear(); memset(whom, -1, sizeof(whom)); memset(p, -1, sizeof(p)); memset(heavy, -1, sizeof(heavy)); memset(is_heavy, 0, sizeof(is_heavy)); k = K; l[0] = 0; depth[0] = 0ll; info_dfs(0); dfs(0); if(ans == 1000000009){ return -1; }else{ return ans; } }

Compilation message (stderr)

race.cpp: In function 'void info_dfs(int)':
race.cpp:56:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |     for(auto& [to, w] : adj[at]){
      |               ^
race.cpp: In function 'void dfs(int)':
race.cpp:84:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   84 |     for(auto& [to, w] : adj[at]){
      |               ^
race.cpp:93:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   93 |     for(auto& [to, w] : adj[at]){
      |               ^
race.cpp:120:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  120 |     for(auto& [to, w] : adj[at]){
      |               ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...