//In His Name
#include <bits/stdc++.h>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2")
using namespace std;
#define ll long long
//#define int ll
typedef pair<int, int> pii;
#define F first
#define S second
#define pb push_back
#define bug(x) cout << "Ah shit , here we go again : " << x <<endl
#define all(x) x.begin() , x.end()
const int maxn = 1e6 + 10 , maxm = 21 , MOD = 1e9 + 7;
const ll INF = 1e9 + 100;
int n , s , t , key[maxm] , door[maxm] , dp[(1<<maxm)][maxm] , mask[maxn] , par[maxn][maxm] , h[maxn] , path[maxm][maxm] , t_path[maxm] , ans = INF;
vector<pii> adj[maxn];
void Dfs(int v , int p){
par[v][0] = p;
for(int i = 1 ; i < maxm ; i++) par[v][i] = par[par[v][i-1]][i-1];
for(pii u : adj[v]){
if(u.F == p) continue;
h[u.F] = h[v]+1;
mask[u.F] = mask[v];
if(u.S != -1){
door[u.S] = v;
mask[u.F] |= (1 << u.S);
}
Dfs(u.F , v);
}
}
int Lca(int a , int b){
if(h[a] < h[b]) swap(a , b);
for(int i = 20 ; i >= 0 ; i--) if(h[par[a][i]] >= h[b]) a = par[a][i];
if(a == b) return a;
for(int i = 20 ; i >= 0 ; i--) if(par[a][i] != par[b][i]) a = par[a][i] , b = par[b][i];
return par[a][0];
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(0) , cout.tie(0);
cin >> n >> s >> t;
int cnt = 0;
for(int i = 1 ; i < n ; i++){
int u , v , w;
cin >> u >> v >> w;
int tmp = -1;
if(w != 0){
tmp = cnt;
key[cnt] = w;
cnt++;
}
adj[u].pb({v , tmp});
adj[v].pb({u , tmp});
}
h[0] = -1;
Dfs(s , 0);
for(int i = 0 ; i < cnt ; i++){
for(int j = 0 ; j < cnt ; j++){
if(i == j) continue;
path[i][j] = h[door[i]] + 2*h[key[j]] + h[door[j]];
int l1 = Lca(door[i] , key[j]) , l2 = Lca(door[j] , key[j]);
path[i][j] -= (2*h[l1] + 2*h[l2]);
}
}
for(int i = 0 ; i < cnt ; i++){
int lca = Lca(t , door[i]) ;
t_path[i] = h[door[i]] + h[t] - 2*h[lca];
}
memset(dp , -1 , sizeof dp);
for(int i = 1 ; i < (1 << cnt); i++){
if(__builtin_popcount(i) == 1){
int u = log2(i&-i);
if(mask[door[u]] == 0 and mask[key[u]] == 0) dp[i][u] = 2*h[key[u]] + h[door[u]];
continue;
}
for(int j = 0 ; j < cnt ; j++){
if((i & (1 << j)) == 0) continue;
int x = i ^ (1 << j);
if((mask[door[j]] & x) != mask[door[j]]) continue;
if((mask[key[j]] & x) != mask[key[j]]) continue;
for(int k = 0 ; k < cnt ; k++){
if(dp[x][k] == -1 or dp[x][k] == INF or k == j) continue;
if(dp[i][j] == -1) dp[i][j] = INF;
dp[i][j] = min(dp[i][j] , dp[x][k] + path[k][j]);
}
if((mask[t] & i) == mask[t] and dp[i][j] != -1) ans = min(dp[i][j] + t_path[j] , ans);
}
}
if(ans == INF) ans = -1;
cout << ans << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
199940 KB |
Output is correct |
| 2 |
Correct |
60 ms |
200072 KB |
Output is correct |
| 3 |
Incorrect |
119 ms |
213816 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
200016 KB |
Output is correct |
| 2 |
Correct |
53 ms |
200020 KB |
Output is correct |
| 3 |
Incorrect |
53 ms |
199936 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
199940 KB |
Output is correct |
| 2 |
Correct |
60 ms |
200072 KB |
Output is correct |
| 3 |
Incorrect |
119 ms |
213816 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
