Submission #783215

#TimeUsernameProblemLanguageResultExecution timeMemory
783215amirhoseinfar1385LOSTIKS (INOI20_lostiks)C++17
36 / 100
911 ms1048576 KiB
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+10,lg=21; struct yal{ int u,v,w; int getad(int fu){ int ret=(u^v^fu); return ret; } }; yal alled[maxn]; vector<int>adj[maxn]; int n,m,lca[lg][maxn*2],wtf[2*maxn],ghabl[maxn],vis[maxn],high[maxn],timea,para[maxn],s,t; pair<int,int>stf[maxn]; int dp[(1<<20)][20]; vector<int>allind[(1<<20)]; vector<int>allv; vector<int>z; void aval(){ for(int i=1;i<(1<<20);i++) { int j=0; for(;;j++){ if((i>>j)&1){ break; } } allind[i]=allind[i^(1<<j)]; allind[i].push_back(j); } int ha=-1; for(int i=1;i<2*maxn;i++){ if(__builtin_popcount(i)==1){ ha++; } wtf[i]=ha; } } void dfs(int u,int par=0){ high[u]=high[par]+1; z.push_back(u); stf[u].first=(int)z.size()-1; for(auto x:adj[u]){ int v=alled[x].getad(u); if(v!=par){ if(v!=alled[x].v){ swap(alled[x].u,alled[x].v); } para[v]=x; dfs(v,u); z.push_back(u); } } stf[u].second=(int)z.size()-1; } void callca(){ for(int i=0;i<lg;i++){ for(int j=0;j<(int)z.size();j++){ if(i==0){ lca[i][j]=z[j]; continue; } if(high[lca[i-1][j]]<high[lca[i-1][j+(1<<(i-1))]]){ lca[i][j]=lca[i-1][j]; } else{ lca[i][j]=lca[i-1][j+(1<<(i-1))]; } } } } int getlca(int u,int v){ int fu=min(stf[u].first,stf[v].first); int fv=max(stf[u].first,stf[v].first); u=fu; v=fv; int len=v-u+1; int te=wtf[len]; if(high[lca[te][u]]<high[lca[te][v-(1<<te)+1]]){ return lca[te][u]; } return lca[te][v-(1<<te)+1]; } int dis(int u,int v){ int uv=getlca(u,v); int ret=high[u]+high[v]-2*high[uv]; return ret; } void solve(int u){ //cout<<u<<endl; if(vis[u]==1){ return ; } solve(alled[para[u]].getad(u)); if(alled[para[u]].w!=0){ allv.push_back(para[u]); solve(alled[para[u]].w); } vis[u]=1; return ; } void calghabl(int u,int par=0){ ghabl[u]+=ghabl[par]; for(auto x:adj[u]){ int v=alled[x].getad(u); if(v!=par){ calghabl(v,u); } } } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); aval(); cin>>n; cin>>s>>t; for(int i=0;i<n-1;i++){ cin>>alled[i].u>>alled[i].v>>alled[i].w; adj[alled[i].u].push_back(i); adj[alled[i].v].push_back(i); } dfs(s); callca(); vis[s]=1; solve(t); m=allv.size(); for(int i=0;i<m;i++){ ghabl[alled[allv[i]].v]+=(1<<i); } calghabl(s); for(int i=1;i<(int)(1<<m);i++){ for(auto x:allind[i]){ int fake=1e9; if((ghabl[alled[allv[x]].u]&i)!=ghabl[alled[allv[x]].u]||(ghabl[alled[allv[x]].w]&i)!=ghabl[alled[allv[x]].w]){ dp[i][x]=fake; continue; } if(__builtin_popcount(i)==1){ dp[i][x]=dis(alled[allv[x]].u,alled[allv[x]].w)+dis(alled[allv[x]].w,s); continue; } for(auto y:allind[i^(1<<x)]){ fake=min(fake,dis(alled[allv[y]].u,alled[allv[x]].w)+dis(alled[allv[x]].u,alled[allv[x]].w)+dp[(1<<x)^i][y]); } dp[i][x]=fake; } } if(m==0){ int res=dis(s,t); cout<<res<<"\n"; return 0; } else{ int res=1e9; for(auto x:allind[(1<<m)-1]){ res=min(res,dp[(1<<m)-1][x]+dis(alled[allv[x]].u,t)); } cout<<res<<"\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...