Submission #789118

#TimeUsernameProblemLanguageResultExecution timeMemory
789118MISM06LOSTIKS (INOI20_lostiks)C++14
0 / 100
2069 ms64924 KiB
//0 1 1 0 1 //0 1 0 0 1 //1 0 0 1 1 //0 1 1 0 1 #include <bits/stdc++.h> #pragma GCC optimize("Ofast,unroll-loops") // #pragma GCC target("avx2") using namespace std; #define F first #define S second #define pb push_back #define sze size() #define all(x) x.begin() , x.end() #define wall__ cout << "--------------------------------------\n"; #define kids int mid = (tl + tr) >> 1, cl = v << 1, cr = v << 1 | 1 #define file_io freopen("input.cpp", "r", stdin); freopen("output.cpp", "w", stdout); typedef long long ll; typedef long double dl; typedef pair < int , int > pii; typedef pair < int , ll > pil; typedef pair < ll , int > pli; typedef pair < ll , ll > pll; typedef pair < int , pii > piii; typedef pair < ll, pll > plll; const ll N = (1 << 20) + 10, M = 23; const ll mod = 1e9 + 7; const ll inf = 2e16; const ll INF = 1e9 + 10; const ll lg = 20; ll n, s, t, h[N], st[N], en[N], m, timer = 0, par[lg][N], id[N], rid[N]; int inp[M * 2][M * 2]; vector < int > g[N]; piii lc[M]; ll dp[M][N]; void dfs (int v, int p) { h[v] = h[p] + 1; st[v] = ++timer; par[0][v] = p; for (int i = 1; i < lg; i++) par[i][v] = par[i - 1][par[i - 1][v]]; for (auto u : g[v]) { if (u == p) continue; dfs(u, v); } en[v] = timer; } bool be_anc (int v, int u) { return (st[v] <= st[u] && en[v] >= en[u]); } int lca (int v, int u) { if (be_anc(v, u)) return v; if (be_anc(u, v)) return u; for (int i = lg - 1; i >= 0; --i) { if (!be_anc(par[i][v], u)) v = par[i][v]; } return par[0][v]; } bool is_in_path (int x, int v, int u) { if (x == v || x == u || x == lca(v, u)) return 1; if (be_anc(x, v) && !be_anc(x, u)) return 1; if (be_anc(x, u) && !be_anc(x, v)) return 1; return 0; } ll dis (int v, int u) { return h[v] + h[u] - 2 * h[lca(v, u)]; } void solve () { cin >> n >> s >> t; for (int i = 1; i < n; i++) { int v, u, w; cin >> v >> u >> w; if (v == u) continue; if (w != 0) { lc[m] = {w, {v, u}}; ++m; } g[v].pb(u); g[u].pb(v); } if (s == t) { cout << 0 << '\n'; return; } en[0] = INF; dfs(s, 0); for (int i = 0; i < m; i++) { if (st[lc[i].S.F] > st[lc[i].S.S]) swap(lc[i].S.F, lc[i].S.S); int v = lc[i].S.F; id[v] = i; rid[i] = v; } id[s] = m; rid[m] = s; id[t] = m + 1; rid[m + 1] = t; for (int i = 0; i < m; i++) { int v = lc[i].F; id[v] = m + 2 + i; rid[m + 2 + i] = v; } for (int i = 0; i <= m + 1 + m; i++) { for (int j = 0; j <= m + 1 + m; j++) { for (int x = 0; x < m; x++) { if (is_in_path(lc[x].S.F, rid[i], rid[j]) && is_in_path(lc[x].S.S, rid[i], rid[j])) inp[i][j] += (1 << x); } } } for (int mask = 0; mask < (1 << m); mask++) { for (int v = 0; v <= m; v++) { dp[v][mask] = inf; if ((mask & inp[v][m + 1]) == 0) dp[v][mask] = dis(rid[v], t); for (int i = 0; i < m; i++) { if (((1 << i) & mask) == 0) continue; int w = lc[i].F; if ((inp[id[w]][v] & mask) == 0 && (inp[id[w]][i] & mask) == 0) { dp[v][mask] = min(dp[v][mask], dp[i][mask ^ (1 << i)] + dis(rid[v], w) + dis(w, rid[i])); } } } } cout << dp[m][(1 << m) - 1]; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int q = 1; // cin >> q; while (q--) {solve();} return 0; } /* */ //shrek is love;
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...