Submission #806749

#TimeUsernameProblemLanguageResultExecution timeMemory
806749ashcompLOSTIKS (INOI20_lostiks)C++14
23 / 100
2080 ms279764 KiB
#include <bits/stdc++.h> using namespace std; #define all(x) x.begin() , x.end() #define pii pair<int,int> #define pll pair<ll,ll> #define F first #define S second #define wall cerr<<"------------------------"<<endl typedef long long ll; const ll INF = 1e9; const ll maxn = 2e6 + 10; const ll mod = 1e9 + 7; int n , m , k , ST , EN , ti; int h[maxn] , p[maxn] , st[maxn] , en[maxn]; int a[maxn<<1] , par[maxn<<1][22] , len[maxn<<1]; vector<int> g[maxn] , LSA; bool mrk[maxn]; void DFS(int v) { mrk[v] = 1; st[v] = ti++; for(auto u : g[v]){ if(mrk[u]==1)continue; p[u] = v; h[u] = h[v]+1; DFS(u); } en[v] = ti++; } inline void pre_LCA() { p[ST] = ST; DFS(ST); for(int j=0; j<21; j++){ for(int i=1; i<=n; i++){ if(j==0){ par[i][j] = p[i]; continue; }else{ int x = par[i][j-1]; par[i][j] = par[x][j-1]; } } } }//OK inline int LCA(int v , int u) { if(st[v]<=st[u]&&en[u]<=en[v])return v; if(st[u]<=st[v]&&en[v]<=en[u])return u; for(int i=20; i>=0; i--){ int x = par[v][i]; if(st[x]>=st[u] || en[u]>=en[x]){ v = x; } } v = p[v]; return v; } inline int DIS(int v , int u) { return (h[v]+h[u]-h[LCA(v,u)]-h[LCA(v,u)]); } vector<pii> eg[maxn]; bool mark[maxn]; int req[maxn]; map<int,int> MP[maxn]; void dfs(int v) { mark[v] = 1; for(auto e : eg[v]){ int u=e.F , w=e.S; if(mark[u]==1)continue; p[u] = v; req[u] = req[v]; if(w!=0){ int x = MP[v][u]; req[u] |= (1<<x); } dfs(u); } } vector<pair<int,pii>> EG; int dp[1<<22][22]; int main() { ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL); cin>>n>>ST>>EN; int ps = 0; for(int i=1; i<n; i++){ int v,u,w; cin>>v>>u>>w; if(w!=0){ MP[v][u] = ps; MP[u][v] = ps; ps++; EG.push_back({w,{v,u}}); } eg[v].push_back({u,w}); eg[u].push_back({v,w}); g[v].push_back(u); g[u].push_back(v); } /**/ pre_LCA(); for(int i=1; i<=n; i++){ p[i] = -1; } dfs(ST); for(int i=1; i<(1<<((int)EG.size()))+(1<<((int)EG.size())); i++){ for(int j=0; j<((int)EG.size())+1; j++){ dp[i][j] = INF; } } for(ll i=1; i<(1<<((int)EG.size())); i++){ int pos = i; while(pos>0){ int j = __builtin_ctz(pos); pos -= (1<<j); int x = i^(1<<j); int V=EG[j].S.F , U=EG[j].S.S , W=EG[j].F; if(req[W]!=(req[W]&x))continue; if(req[V]!=(req[V]&x) && req[U]!=(req[U]&x))continue; if(x==0){ dp[i][j] = DIS(ST,W) + min(DIS(W,V),DIS(W,U)); continue; } int POS=i; while(POS>0){ int f = __builtin_ctz(POS); POS -= 1<<f; int v=EG[f].S.F , u=EG[f].S.S; int D1=DIS(ST,v) , D2=DIS(ST,u); if(D1>D2){ swap(v,u); } dp[i][j] = min(dp[i][j] , dp[x][f]+DIS(v,W)+min(DIS(W,V),DIS(W,U)) ); } } } /***********************************/ ps = ((int)EG.size()); eg[EN].push_back({n+1,EN}); eg[n+1].push_back({EN,EN}); MP[EN][n+1] = ps; MP[EN][n+1] = ps; EG.push_back({EN,{EN,n+1}}); for(ll i=(1<<ps); i<(1<<(ps+1)); i++){ int j = ps; int x = i^(1<<j); int V=EG[j].S.F , U=EG[j].S.S , W=EG[j].F; if(req[W]!=(req[W]&x))continue; if(req[V]!=(req[V]&x) && req[U]!=(req[U]&x))continue; if(x==0){ dp[i][j] = DIS(ST,W) + min(DIS(W,V),DIS(W,U)); continue; } int POS=i; while(POS>0){ int f = __builtin_ctz(POS); POS -= 1<<f; int v=EG[f].S.F , u=EG[f].S.S; int D1=DIS(ST,v) , D2=DIS(ST,u); if(D1>D2){ swap(v,u); } dp[i][j] = min(dp[i][j] , dp[x][f]+DIS(v,W)+min(DIS(W,V),DIS(W,U)) ); } } int ans = INF; for(int i=(1<<ps); i<(1<<(ps+1)); i++){ ans = min(ans , dp[i][ps]); } /*ll ans = INF; for(int i=1; i<(1<<((int)EG.size())); i++) { for(int j=0; j<((int)EG.size()); j++){ int V=EG[j].S.F , U=EG[j].S.S; if(DIS(V,ST)>DIS(U,ST)){ swap(V,U); } if(req[EN]!=(req[EN]&i))continue; ans = min(ans , (ll)dp[i][j] + DIS(V,EN)); } }*/ if(ans==INF){ cout<<-1; return 0; } cout<<ans; return 0; } /* 3 1 3 1 2 3 1 3 2 */ /* 10 1 10 1 2 0 2 3 0 3 4 0 4 5 2 2 6 4 2 7 0 7 8 5 8 9 6 9 10 0 ans = 19 */ /** 4 1 4 1 2 0 1 3 2 3 4 1 ans = 4; */ /* 5 3 1 1 2 5 2 3 4 3 4 0 4 5 2 ans = 10; */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...