Submission #802393

#TimeUsernameProblemLanguageResultExecution timeMemory
802393ashcompLOSTIKS (INOI20_lostiks)C++14
0 / 100
248 ms191608 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 = 1e18; const ll maxn = 1e6 + 10; const ll mod = 1e9 + 7; int n , m , k , ST , EN; int h[maxn] , p[maxn] , st[maxn] , en[maxn]; int a[maxn<<1] , rmq[maxn<<1][21] , ps_rmq[maxn<<1][21] , rrmq[maxn<<1][21] , ps_rrmq[maxn<<1][21] , len[maxn<<1]; vector<int> g[maxn] , LSA; bool mrk[maxn]; void DFS(int v) { mrk[v] = 1; LSA.push_back(v); st[v] = LSA.size()-1; for(auto u : g[v]){ if(mrk[u]==1)continue; p[u] = v; h[u] = h[v]+1; DFS(u); LSA.push_back(v); } if(g[v].size()==1 && v!=1){ LSA.push_back(v); } en[v] = LSA.size()-1; } void pre_LCA() { LSA.push_back(0); p[1] = -1; DFS(1); m = LSA.size()-1; for(int i=1; i<=m; i++){ a[i] = h[LSA[i]]; } for(int j=0; j<21; j++){ for(int i=1; i<=m; i++){ if(j==0){ rmq[i][j] = a[i]; rrmq[i][j] = a[i]; ps_rmq[i][j] = i; ps_rrmq[i][j] = i; continue; } if((i+(1<<j)-1)<=m){ rmq[i][j] = rmq[i][j-1]; ps_rmq[i][j] = ps_rmq[i][j-1]; if(rmq[i][j-1] > rmq[i+(1<<(j-1))][j-1]){ rmq[i][j] = rmq[i+(1<<(j-1))][j-1]; ps_rmq[i][j] = ps_rmq[i+(1<<(j-1))][j-1]; } } if((i-(1<<j)+1)>0){ rrmq[i][j] = rrmq[i][j-1]; ps_rrmq[i][j] = ps_rrmq[i][j-1]; if(rrmq[i][j-1] > rrmq[i-(1<<(j-1))][j-1]){ rrmq[i][j] = rrmq[i-(1<<(j-1))][j-1]; ps_rrmq[i][j] = ps_rrmq[i-(1<<(j-1))][j-1]; } } } } int PS = 0; for(int i=1; i<=m; i++){ if(((1<<PS)<<1)<i){ PS++; } len[i] = PS; } } int LCA(int v , int u) { int l = min(st[v],st[u]) , r=max(en[v],en[u]); int ln = len[r-l+1]; int x = rmq[l][ln] , y = rrmq[r][ln]; if(x < y){ int pos = ps_rmq[l][ln]; return LSA[pos]; }else{ int pos = ps_rrmq[r][ln]; return LSA[pos]; } } int times=0; map<int,bool> mp[maxn]; bool mark[maxn][30]; vector<int> ORDER; vector<pii> eg[maxn]; int dfs(int v , int tm , int end) { //cout<<v<<"-->"<<end<<" : "<<tm<<"\n"; if(tm>50){ return -1; } if(v==end){ return 1; } mark[v][tm] = 1; for(auto e : eg[v]){ int u=e.F , w=e.S; int now = h[end]+h[v]-h[LCA(end,v)]-h[LCA(end,v)]; int then = h[end]+h[u]-h[LCA(end,u)]-h[LCA(end,u)]; if(then < now){ if(w==0){ dfs(u,tm,end); }else{ if(mp[v][u]==0){ int tp = dfs(v,tm+1,w); if(tp==-1){ return -1; } ORDER.push_back(w); ORDER.push_back(v); mp[v][u] = 1; mp[u][v] = 1; int x=dfs(u,tm,end); }else{ int x=dfs(u,tm,end); } } } } return 1; } int DIS(int v , int u) { return (h[v]+h[u]-h[LCA(v,u)]-h[LCA(v,u)]); } int main() { ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL); cin>>n>>ST>>EN; for(int i=1; i<n; i++){ int v,u,w; cin>>v>>u>>w; if(w==0){ //mp[v][u] = 1; //mp[u][v] = 1; } eg[v].push_back({u,w}); eg[u].push_back({v,w}); g[v].push_back(u); g[u].push_back(v); } pre_LCA(); ORDER.push_back(ST); int tp = dfs(ST,1,EN); ORDER.push_back(EN); if(tp==-1){ cout<<"-1"; }else{ ll ans = 0 , sz=ORDER.size(); for(int i=1; i<sz; i++){ int v = ORDER[i-1] , u=ORDER[i]; ans += h[v]+h[u]-h[LCA(v,u)]-h[LCA(v,u)]; } cout<<ans; } return 0; } /* 6 1 6 1 2 0 1 3 0 3 4 0 4 5 2 5 6 1 ans = 10; */ /** 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; */

Compilation message (stderr)

Main.cpp: In function 'int dfs(int, int, int)':
Main.cpp:132:45: warning: unused variable 'x' [-Wunused-variable]
  132 |                                         int x=dfs(u,tm,end);
      |                                             ^
Main.cpp:134:45: warning: unused variable 'x' [-Wunused-variable]
  134 |                                         int x=dfs(u,tm,end);
      |                                             ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...