Submission #946245

#TimeUsernameProblemLanguageResultExecution timeMemory
946245PM1LOSTIKS (INOI20_lostiks)C++17
0 / 100
63 ms42672 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define fr first #define sc second const int mxn=1e6+5,sz=(1<<20); int n,dis[40][40],par[mxn][22],c[mxn],key[25],door[25],cnt=0,d[mxn]; ll dp[sz][25],ans=1e9; vector<pair<int,int>>v[mxn]; void dfs(int z,int f=0){ for(int i=1;i<=20;i++) par[z][i]=par[par[z][i-1]][i-1]; for(auto i:v[z]){ if(par[z][0]!=i.fr){ par[i.fr][0]=z; c[i.fr]=c[z]; d[i.fr]=d[z]+1; if(i.sc){ door[++cnt]=z; key[cnt]=i.sc; c[i.fr]|=(1<<(cnt-1)); } dfs(i.fr); } } } int lca(int x,int y){ if(x==0 || y==0)return 0; if(d[x]<d[y])swap(x,y); int res=0; for(int i=20;i>=0;i--){ if((1<<i)<=d[x]-d[y])x=par[x][i],res+=(1<<i); } if(x==y)return res; for(int i=20;i>=0;i--){ if(par[x][i]!=par[y][i])x=par[x][i],y=par[y][i],res+=(1<<(i+1)); } return res+2; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n; cin>>door[21]>>key[21]; for(int i=1;i<n;i++){ int x,y,w; cin>>x>>y>>w; v[x].push_back({y,w}); v[y].push_back({x,w}); } dfs(door[21]); for(int i=1;i<=21;i++){ for(int j=1;j<=21;j++){ dis[i][j]=lca(door[i],key[j]); } } for(int i=0;i<cnt;i++){ if(!c[door[i+1]] && !c[key[i+1]]) dp[(1<<i)][i]=dis[21][i+1]+dis[i+1][i+1]; else dp[(1<<i)][i]=1e9; if(((1<<i)&(c[key[21]]))==c[key[21]]) ans=min(ans,dp[(1<<i)][i]+dis[i+1][21]); } for(int i=2;i<(1<<cnt);i++){ for(int j=0;j<cnt;j++){ dp[i][j]=1e9; if((i&(1<<j)) && (i&c[door[j+1]])==c[door[j+1]] && (i&c[key[j+1]])==c[key[j+1]]) { for(int w=0;w<cnt;w++){ if(i&(1<<w)){ if(w!=j ){ dp[i][j]=min(dp[i][j],dis[j+1][j+1]+dis[w+1][j+1]+dp[i-(1<<j)][w]); } } } if((i&(c[key[21]]))==c[key[21]]){ ans=min(ans,dp[i][j]+dis[j+1][21]); } } } } if(c[key[21]]==0)ans=dis[21][21]; assert(ans<=1e9 ); cout<<ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...