제출 #430235

#제출 시각아이디문제언어결과실행 시간메모리
430235Odavey경주 (Race) (IOI11_race)C++17
9 / 100
330 ms26980 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]; ll depth[MX_N]; int gl_tit = 0; int gl_dit = 0; vector<pair<int, ll> > adj[MX_N]; void info_dfs(int at){ card[at] = 1; whom[gl_tit] = at; tin[at] = gl_tit++; 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[heavy[at]] < card[to]){ heavy[at] = to; } } } if(heavy[at] != -1){ is_heavy[heavy[at]] = true; } 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){ 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{ l_q[d_id[depth[whom[i]]]][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{ l_q[d_id[depth[at]]][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){ 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; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...