제출 #429444

#제출 시각아이디문제언어결과실행 시간메모리
429444Odavey경주 (Race) (IOI11_race)C++17
21 / 100
483 ms39096 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; heavy[at] = -1; is_heavy[at] = false; 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; } //cout << "With god as my witness, a = " << a << ", db & lb = " << db << " & " << lb << ", giving " << l[a] + lb - 2*l[at] << " length(s)\n"; 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; } //cout << "With god as my witness, a = " << a << ", db & lb = " << db << " & " << lb << ", giving " << l[a] + lb - 2*l[at] << " length(s)\n"; 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]]]--; } } 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}); } k = K; l[0] = 0; depth[0] = 0; info_dfs(0); dfs(0); if(ans == 1000000009){ return -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...