This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define debug(x) cout << #x << "= " << x << ", "
#define ll long long
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define SZ(x) (int) x.size()
#define wall cout << endl;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1e6 + 10 , maxm = 21 , inf = 1e9;
int n , key[maxm] , s , t , t_path[maxm] , door[maxm] , par[maxm][maxn] , dis[maxn] , path[maxm][maxm];
int mask[maxn] , dp[maxm][(1 << maxm)] , ps;
struct edge{
int v , lock;
};
vector <edge> adj[maxn];
void dfs(int v)
{
for(auto u : adj[v]) if(u.v != par[0][v])
{
par[0][u.v] = v;
dis[u.v] = dis[v] + 1;
mask[u.v] = mask[v];
if(u.lock != -1)
{
door[u.lock] = v;
mask[u.v] |= (1 << u.lock);
}
dfs(u.v);
}
}
int lca(int a , int b)
{
if(dis[a] < dis[b]) swap(a , b);
for(int i = 0 ; i < maxm ; i++) if(((dis[a] - dis[b]) >> i) & 1) a = par[i][a];
if(a == b) return a;
for(int i = maxm - 1 ; i > -1 ; i--) if(par[i][a] != par[i][b])
{
a = par[i][a]; b = par[i][b];
}
return par[0][a];
}
void solve(int v , int msk)
{
if(dp[v][msk] != -1) return;
if(!(mask[t] & msk))
{
dp[v][msk] = t_path[v];
return;
}
dp[v][msk] = inf;
for(int i = 0 ; i < ps ; i++) if(((msk >> i) & 1))
{
int tmask = (mask[key[i]] | mask[door[i]]);
if(!(tmask & msk))
{
solve(i , (msk ^ (1 << i)));
dp[v][msk] = min(dp[v][msk] , dp[i][(msk ^ (1 << i))] + path[v][i]);
}
}
}
int32_t main()
{
fast;
cin >> n;
cin >> s >> t;
for(int i = 0 ; i < n - 1 ; i++)
{
int v , u , w; cin >> v >> u >> w;
int tmp = -1;
if(w != 0)
{
tmp = ps;
key[ps] = w;
ps++;
}
adj[v].pb({u , tmp}); adj[u].pb({v , tmp});
}
door[ps] = s;
dfs(s);
for(int i = 1 ; i < maxm ; i++)
for(int j = 1 ; j <= n ; j++)
par[i][j] = par[i - 1][par[i - 1][j]];
for(int i = 0 ; i <= ps ; i++) for(int j = 0 ; j < ps ; j++) if(i != j)
{
path[i][j] = dis[door[i]] + dis[key[j]] + dis[key[j]] + dis[door[j]];
int l1 = lca(door[i] , key[j]) , l2 = lca(door[j] , key[j]);
path[i][j] -= (dis[l1] + dis[l2] + dis[l2] + dis[l1]);
}
for(int i = 0 ; i <= ps ; i++)
{
int l = lca(t , door[i]); t_path[i] = dis[door[i]] + dis[t] - dis[l] - dis[l];
}
memset(dp , -1 , sizeof dp);
solve(ps , (1 << ps) - 1);
cout << dp[ps][(1 << ps) - 1] << endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |