Submission #1261650

#TimeUsernameProblemLanguageResultExecution timeMemory
1261650Hamed_GhaffariLOSTIKS (INOI20_lostiks)C++20
0 / 100
57 ms34292 KiB
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; #define X first #define Y second #define mins(a, b) (a = min(a,b)) const int MXN = 1e6+2, MXM = 20, inf = 1e9; int n, m, s, t; vector<pii> g[MXN]; int dis[MXM+2][MXN], dp[1<<MXM][MXM], id[MXN], mask[MXM+1][MXN]; vector<int> vec; void dfs(int wh, int v, int p=0) { for(auto [u, w] : g[v]) if(u!=p) { dis[wh][u] = dis[wh][v]+1; mask[wh][u] = mask[wh][v] | (w ? (1<<id[w]) : 0); dfs(wh, u, v); } } inline bool is_sub(int x, int y) { return (x&y)==x; } int32_t main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); cin >> n >> s >> t; for(int i=0, u,v,w; i<n-1; i++) { cin >> u >> v >> w; g[u].push_back({v, w}); g[v].push_back({u, w}); if(w) vec.push_back(w); } sort(vec.begin(), vec.end()); m = unique(vec.begin(), vec.end())-vec.begin(); vec.resize(m); for(int i=0; i<m; i++) id[vec[i]] = i; for(int i=0; i<m; i++) dfs(i, vec[i]); dfs(m, s); if(!mask[m][t]) { cout << dis[m][t] << '\n'; return 0; } for(int msk=0; msk<(1<<m); msk++) fill(dp[msk], dp[msk]+m, inf); for(int i=0; i<m; i++) if(!mask[m][vec[i]]) dp[1<<i][i] = dis[m][vec[i]]; for(int msk=1; msk<(1<<m)-1; msk++) for(int i=0; i<m; i++) if(msk>>i&1) for(int j=0; j<m; j++) if(!(msk>>j&1)) if(is_sub(mask[i][vec[j]], msk)) mins(dp[msk^(1<<j)][j], dp[msk][i] + dis[i][vec[j]]); int ans = inf; for(int msk=1; msk<(1<<m); msk++) for(int i=0; i<m; i++) if((msk>>i&1) && is_sub(mask[i][t], msk)) mins(ans, dp[msk][i] + dis[i][t]); cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...