Submission #999198

#TimeUsernameProblemLanguageResultExecution timeMemory
999198vjudge1LOSTIKS (INOI20_lostiks)C++17
0 / 100
2074 ms132192 KiB
#include <bits/stdc++.h> #define ll long long #define endl "\n" using namespace std; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); const ll N = 1e6 + 5, lg = 22; vector<pair<ll, ll>> g[N]; ll need[N], comp[N], depth[N], up[lg][N]; ll vals[lg], dp[1 << lg][lg]; ll freq[lg][N]; void dfs(ll v, ll par = 0) { up[0][v] = par; for (ll i = 1; i < lg; i++) up[i][v] = up[i - 1][up[i - 1][v]]; for (auto [to, w] : g[v]) if (to != par) { for (ll i = 0; i < lg; i++) freq[i][to] = freq[i][v]; if (w) freq[comp[w]][to]++; depth[to] = depth[v] + 1; dfs(to, v); } } ll lca(ll a, ll b) { if (depth[a] < depth[b]) swap(a, b); for (ll bit = lg - 1; bit >= 0; bit--) if (depth[a] - (1 << bit) >= depth[b]) a = up[bit][a]; if (a == b) return a; for (ll bit = lg - 1; bit >= 0; bit--) if (up[bit][a] != up[bit][b]) a = up[bit][a], b = up[bit][b]; return up[0][a]; } ll dist(ll a, ll b) { return depth[a] + depth[b] - depth[lca(a, b)] * 2; } ll needs(ll a, ll b) { ll lc = lca(a, b), ans = 0; for (ll i = 0; i < lg; i++) if (freq[i][a] + freq[i][b] - freq[i][lc] * 2) ans |= 1 << i; return ans; } void solve() { ll n; cin >> n; ll s, t; cin >> s >> t; array<ll, 3> e[n - 1]; for (ll i = 0; i < n - 1; i++) { cin >> e[i][0] >> e[i][1] >> e[i][2]; g[e[i][0]].push_back(make_pair(e[i][1], e[i][2])); g[e[i][1]].push_back(make_pair(e[i][0], e[i][2])); } ll sz = 0; { set<ll> tmp; for (ll i = 1; i <= n; i++) for (auto [j, w] : g[i]) if (w) tmp.insert(w); tmp.insert(s); tmp.insert(t); for (ll i : tmp) comp[i] = sz, vals[sz++] = i; } dfs(s, s); // for (ll i = 0; i < (1 << sz); i++) // for (ll j = 0; j < sz; j++) // dp[i][j] = 1e18; // dp[1 << comp[s]][comp[s]] = 0; // for (ll msk = 0; msk < (1 << sz); msk++) if (msk != (1 << comp[s])) // { // for (ll i = 0; i < sz; i++) // if (msk >> i & 1) // for (ll j = 0, x; j < sz; j++) // { // x = needs(vals[i], vals[j]); // if ((msk >> j & 1) and j != i and ((msk ^ (1 << i)) & x) == x) // dp[msk][i] = min(dp[msk][i], dp[msk ^ (1 << i)][j] + dist(vals[i], vals[j])); // } // } // ll ans = 1e18; // for (ll msk = 0; msk < (1 << sz); msk++) // ans = min(ans, dp[msk][comp[t]]); // if (ans == 1e18) // ans = -1; // cout << ans << endl; ll ans = 1e18; for (ll msk = 0; msk < (1 << sz); msk++) if ((msk & 1) and (msk & (1 << (sz - 1)))) do { if (vals[0] != s or vals[sz - 1] != t) continue; ll cur = 1 << comp[vals[0]], res = 0, last = vals[0]; bool ok = true; for (ll i = 1, x; i < sz; i++) if (msk >> i & 1) { x = needs(vals[i], last); if ((cur & x) != x) { ok = false; break; } res += dist(vals[i], last); cur |= 1 << comp[vals[i]]; last = vals[i]; } if (ok) ans = min(ans, res); } while (next_permutation(vals, vals + sz)); if (ans == 1e18) ans = -1; cout << ans << endl; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); ll t = 1; // precomp(); // cin >> t; for (ll cs = 1; cs <= t; cs++) solve(); // cerr << "\nTime elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...