Submission #953839

#TimeUsernameProblemLanguageResultExecution timeMemory
953839angellaLOSTIKS (INOI20_lostiks)C++17
0 / 100
71 ms76736 KiB
/* 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], 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]; } } 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])); if(i==j) continue; } 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=1; i<=m; i++) { dp[(1<<(i-1))][i] = 1e9; 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) { dp[mask][i] = 1e9; 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((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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...