Submission #782028

#TimeUsernameProblemLanguageResultExecution timeMemory
782028amirhoseinfar1385LOSTIKS (INOI20_lostiks)C++17
0 / 100
11 ms24008 KiB
#include<bits/stdc++.h> using namespace std; struct yal{ int u,v,w; int getad(int fu){ int ret=(u^v^fu); return ret; } }; const int maxn=1000000+10,lg=21; yal alled[maxn]; vector<int>adj[maxn]; int vis[maxn],n,s,t; int lca[lg][maxn],par[maxn],high[maxn],timea=0; pair<int,int>stf[maxn]; void dfs(int u,int para=0){ lca[0][u]=para; timea++; stf[u].first=timea; high[u]=high[para]+1; for(auto x:adj[u]){ int v=alled[x].getad(u); if(v!=para){ par[v]=x; dfs(v,u); } } stf[u].second=timea; } void callca(){ for(int i=1;i<lg;i++){ for(int j=1;j<=n;j++){ lca[i][j]=lca[i-1][lca[i-1][j]]; } } } int last=0; int zird(int u,int v){ if(stf[v].first<=stf[u].first&&stf[v].second>=stf[u].second){ return 1; } return 0; } int getlca(int u,int v){ if(zird(u,v)){ return v; } if(zird(v,u)){ return u; } for(int i=lg-1;i>=0;i--){ if(lca[i][u]!=0&&zird(v,lca[i][u])==0){ u=lca[i][u]; } } u=lca[0][u]; return u; } long long dis(int u,int v){ int uv=getlca(u,v); int ret=high[u]+high[v]-2*high[uv]; return ret; } long long solve(int u){ if(vis[u]==1){ long long ret=dis(last,u); last=u; return 0; } long long ret=solve(alled[par[u]].getad(u)); //cout<<u<<" "<<par[u]<<" "<<alled[par[u]].w<<"\n"; if(alled[par[u]].w!=0){ ret+=solve(alled[par[u]].w); } ret+=dis(last,u); last=u; vis[u]=1; // cout<<u<<" "<<ret<<"\n"; return ret; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 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(); last=s; vis[s]=1; cout<<solve(t)<<"\n"; }

Compilation message (stderr)

Main.cpp: In function 'long long int solve(int)':
Main.cpp:72:13: warning: unused variable 'ret' [-Wunused-variable]
   72 |   long long ret=dis(last,u);
      |             ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...