/*
IN THE NAME OF GOD
*/
#include <bits/stdc++.h>
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;
#define F first
#define S second
#define Mp make_pair
#define pb push_back
#define pf push_front
#define size(x) ((ll)x.size())
#define all(x) (x).begin(),(x).end()
#define kill(x) cout << x << '\n', exit(0);
#define fuck(x) cout << "(" << #x << " , " << x << ")" << endl
#define endl '\n'
const int N = 1e6+23, lg = 20;
ll Mod = 1e9+7; //998244353;
inline ll MOD(ll a, ll mod=Mod) {a%=mod; (a<0)&&(a+=mod); return a;}
inline ll poww(ll a, ll b, ll mod=Mod) {
ll ans = 1;
a=MOD(a, mod);
while (b) {
if (b & 1) ans = MOD(ans*a, mod);
b >>= 1;
a = MOD(a*a, mod);
}
return ans;
}
int n, s, t, m, tim, nd[22][22], dp[(1<<20)][21], par[lg][N];
int arr[22][5], mark[N], h[N], dst[22][22], tin[N], tout[N];
vector<int> adj[N];
void init(int v, int p=0) {
tin[v] = ++tim, par[0][v] = p, h[v] = h[p] + 1;
for(int i=1; i<lg; i++) par[i][v] = par[i-1][par[i-1][v]];
for(int u : adj[v]) {
if(u == p) continue;
init(u, v);
}
tout[v] = tim+1;
}
int getPar(int v, int dist) {
for(int i=0; i<lg; i++) if((dist>>i)%2 == 1) v = par[i][v];
return v;
}
int LCA(int v, int u) {
if(h[v] > h[u]) swap(v, u);
u = getPar(u, h[u] - h[v]);
if(v == u) return v;
for(int i=lg-1; i>=0; i--) {
if(par[i][v] != par[i][u]) {
v = par[i][v], u = par[i][u];
}
}
return par[0][v];
}
int calc(int v, int u) {
int lca = LCA(v, u);
return h[v]+h[u]-2*h[lca];
}
bool insub(int v, int u) {
if(tin[v] <= tin[u] && tout[v] > tin[u]) return true;
return false;
}
bool isinpath(int w, int v, int u) {
int lca = LCA(v, u);
if(insub(lca,w)==1&&(insub(w,v)==1||insub(w,u)==1)) return 1;
return 0;
}
int calc2(int v, int u) {
int res = 0;
for(int i=1; i<=m; i++) {
if(isinpath(arr[i][4],v,u)==1) {
res |= (1<<(i-1));
}
}
return res;
}
int main () {
ios_base::sync_with_stdio(false), cin.tie(0);
cin>>n>>s>>t;
for(int v,u,w,i=1; i<n; i++) {
cin>>v>>u>>w;
adj[v].pb(u); adj[u].pb(v);
if(w > 0) {
m++;
arr[m][3]=w, arr[m][0]=v, arr[m][1]=u;
}
}
init(1);
for(int i=1; i<=m; i++) {
if(calc(arr[i][0], s) < calc(arr[i][1], s)) {
arr[i][2] = arr[i][0];
arr[i][4] = arr[i][1];
} else {
arr[i][2] = arr[i][1];
arr[i][4] = arr[i][0];
}
mark[arr[i][4]] = 1;
}
if(calc2(s, t) == 0) kill(calc(s, t));
for(int i=1; i<=m; i++) {
for(int j=1; j<=m; j++) {
dst[i][j] = calc(arr[i][2], arr[j][3]) + calc(arr[j][3], arr[j][2]);
nd[i][j] = (calc2(arr[i][2], arr[j][3]) | calc2(arr[j][3], arr[j][2]));
}
nd[0][i] = calc2(s, arr[i][2]);
nd[i][m+1] = calc2(arr[i][2], t);
}
for(int i=0; i<=m+1; i++) {
for(int j=0; j<=m+1; j++) {
int v = (i==0?s:(i==m+1?t:arr[i][2]));
int u = (j==0?s:(j==m+1?t:arr[j][2]));
if(i!=0 && i!=m+1 && j!=0 && j!=m+1) continue;
if(i==0&&j<=m) {
dst[i][j] = calc(v, arr[j][3]) + calc(arr[j][3], arr[j][2]);
} else {
dst[i][j] = calc(v, u);
}
}
}
for(int i=0; i<(1<<m); i++) fill(dp[i],dp[i]+21,1e9);
for(int i=1; i<=m; i++) {
if(nd[0][i] == 0) {
dp[(1<<(i-1))][i] = dst[0][i];
}
}
int ans = 1e9;
for(int mask=1; mask<(1<<m); mask++) {
for(int i=1; i<=m; i++) {
if((mask>>(i-1))%2==0) continue;
if(__builtin_popcount(mask) > 1) {
dp[mask][i] = 1e9;
int mask2 = mask - (1<<(i-1));
for(int j=1; j<=m; j++) {
if((mask2>>(j-1))%2==0) continue;
//int mask3 = mask2 - (1<<(j-1));
if((nd[j][i]&mask2) == nd[j][i]) {
dp[mask][i] = min(dp[mask][i], dp[mask2][j]+dst[j][i]);
}
}
}
if(mark[t] == 1) {
if(arr[i][4]==t)ans = min(ans, dp[mask][i]+1);
} else if((nd[i][m+1]&mask)==nd[i][m+1]) ans = min(ans, dp[mask][i]+dst[i][m+1]);
}
}
//fuck(nd[1][2]);
cout<<(ans==1e9 ? -1 : ans)<<endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
72272 KB |
Output is correct |
| 2 |
Correct |
12 ms |
72284 KB |
Output is correct |
| 3 |
Correct |
59 ms |
84280 KB |
Output is correct |
| 4 |
Correct |
57 ms |
84308 KB |
Output is correct |
| 5 |
Correct |
58 ms |
84500 KB |
Output is correct |
| 6 |
Correct |
56 ms |
84360 KB |
Output is correct |
| 7 |
Correct |
56 ms |
84324 KB |
Output is correct |
| 8 |
Correct |
57 ms |
84292 KB |
Output is correct |
| 9 |
Correct |
54 ms |
84304 KB |
Output is correct |
| 10 |
Correct |
75 ms |
84228 KB |
Output is correct |
| 11 |
Correct |
57 ms |
84388 KB |
Output is correct |
| 12 |
Incorrect |
54 ms |
85016 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
72280 KB |
Output is correct |
| 2 |
Correct |
11 ms |
72440 KB |
Output is correct |
| 3 |
Correct |
11 ms |
72284 KB |
Output is correct |
| 4 |
Incorrect |
11 ms |
72284 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
72272 KB |
Output is correct |
| 2 |
Correct |
12 ms |
72284 KB |
Output is correct |
| 3 |
Correct |
59 ms |
84280 KB |
Output is correct |
| 4 |
Correct |
57 ms |
84308 KB |
Output is correct |
| 5 |
Correct |
58 ms |
84500 KB |
Output is correct |
| 6 |
Correct |
56 ms |
84360 KB |
Output is correct |
| 7 |
Correct |
56 ms |
84324 KB |
Output is correct |
| 8 |
Correct |
57 ms |
84292 KB |
Output is correct |
| 9 |
Correct |
54 ms |
84304 KB |
Output is correct |
| 10 |
Correct |
75 ms |
84228 KB |
Output is correct |
| 11 |
Correct |
57 ms |
84388 KB |
Output is correct |
| 12 |
Incorrect |
54 ms |
85016 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
