Submission #802584

#TimeUsernameProblemLanguageResultExecution timeMemory
802584ashcompLOSTIKS (INOI20_lostiks)C++14
0 / 100
263 ms196176 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<<2] , rmq[maxn<<2][25] , ps_rmq[maxn<<2][25] , rrmq[maxn<<2][25] , ps_rrmq[maxn<<2][25] , len[maxn<<2]; 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); } 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<25; 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(st[v],st[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]; vector<int> ORDER; vector<pii> eg[maxn]; int dfs(int v , int tm , int end) { //cout<<v<<"-->"<<end<<" : "<<tm<<"\n"; if(times>20){ return -1; } if(v==end){ return 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){ int tp = dfs(u,tm,end); if(tp==-1)return -1; }else{ if(mp[v][u]==0){ times++; int tp = dfs(v,times,w); if(tp==-1){ return -1; } ORDER.push_back(w); ORDER.push_back(v); mp[v][u] = 1; mp[u][v] = 1; tp = dfs(u,tm,end); if(tp==-1)return -1; }else{ int tp = dfs(u,tm,end); if(tp==-1)return -1; } } } } return 1; } 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){ while(n>0){ cout<<"-1"<<endl; } }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; */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...