Submission #624111

#TimeUsernameProblemLanguageResultExecution timeMemory
624111ArinoorLOSTIKS (INOI20_lostiks)C++17
36 / 100
318 ms270000 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define fi first #define se second #define all(x) x.begin(), x.end() #define bug(x) cout << #x << " : " << x << '\n' #define ios ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0) typedef long long ll; typedef pair<int, int> pii; const int maxn = 1e6 + 10; const int maxm = 30; const int maxlg = 20; const int mod = 1e9 + 7; const ll inf = 1e17 + 10; int e[maxn], h[maxn], par[maxn][maxlg], lck[maxn][maxlg], V[maxm], ind[maxn]; int dt[maxm], dl[maxm]; int d[maxm][maxm], l[maxm][maxm]; ll dp[1 << maxlg][maxm]; vector<pii> E; vector<pii> edge; vector<int> G[maxn], S; void dfs(int v, int p = 0, int pe = -1){ par[v][0] = p; if(~pe) lck[v][0] = 1 << pe; for(int i = 1; i < maxlg and par[v][i - 1]; i ++){ par[v][i] = par[par[v][i - 1]][i - 1]; lck[v][i] = lck[v][i - 1] | lck[par[v][i - 1]][i - 1]; } for(int eg : G[v]){ int u = edge[eg].fi + edge[eg].se - v; if(u != p){ h[u] = h[v] + 1; dfs(u, v, e[eg]); } } } int get_par(int v, int h){ for(int i = 0; i < maxlg; i ++) if(h >> i & 1) v = par[v][i]; return v; } int get_lock(int v, int h){ int res = 0; for(int i = 0; i < maxlg; i ++){ if(h >> i & 1){ res |= lck[v][i]; v = par[v][i]; } } return res; } int lca(int v, int u){ if(h[v] < h[u]) swap(u, v); v = get_par(v, h[v] - h[u]); if(v == u) return v; for(int i = maxlg - 1; ~i; i --){ if(par[v][i] ^ par[u][i]){ v = par[v][i]; u = par[u][i]; } } return par[v][0]; } int dist(int u, int v){ int w = lca(u, v); return h[v] + h[u] - 2 * h[w]; } int lock_path(int u, int v){ int w = lca(u, v); return get_lock(u, h[u] - h[w]) | get_lock(v, h[v] - h[w]); } int main(){ ios; int n, s, t; cin >> n >> s >> t; for(int i = 0; i < n - 1; i ++){ int u, v, w; cin >> u >> v >> w; edge.pb(mp(u, v)); G[u].pb(i); G[v].pb(i); if(w){ e[i] = E.size(); E.pb(mp(i, w)); } else{ e[i] = -1; } } dfs(1); int m = E.size(); for(int i = 0; i < m; i ++){ int u = edge[E[i].fi].fi; int v = edge[E[i].fi].se; if(dist(E[i].se, u) < dist(E[i].se, v)) V[i] = u; else V[i] = v; S.pb(V[i]); } S.pb(s); sort(all(S)); S.resize(unique(all(S)) - S.begin()); for(int v : S) ind[v] = lower_bound(all(S), v) - S.begin(); n = S.size(); for(int i = 0; i < n; i ++){ int v = S[i]; dt[i] = dist(v, t); dl[i] = lock_path(v, t); for(int j = 0; j < m; j ++){ int u = V[j]; int w = E[j].se; d[i][j] = dist(v, w) + dist(w, u); l[i][j] = lock_path(v, w) | lock_path(w, u); } } for(int msk = 0; msk < 1 << m; msk ++){ for(int i = 0; i < n; i ++){ if(!(dl[i] & msk)){ dp[msk][i] = dt[i]; continue; } dp[msk][i] = inf; for(int msk2 = msk; ; msk2 -= msk2 & -msk2){ if(!msk2) break; int bit = __builtin_ctz(msk2); if(!(l[i][bit] & msk)){ dp[msk][i] = min(dp[msk][i], d[i][bit] + dp[msk ^ (1 << bit)][ind[V[bit]]]); } } } } cout << dp[(1 << m) - 1][ind[s]] << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...