Submission #697349

#	Time	Username	Problem	Language	Result	Execution time	Memory
697349		manizare	Valley (BOI19_valley)	C++14	100 / 100	259 ms	89988 KiB

valley

#include <bits/stdc++.h> 
#define int long long 
#define pb push_back 
#define F first 
#define S second 
#define all(a) a.begin(),a.end() 
#define pii pair<int,int> 

using namespace std ;
const int maxn =  5e5 + 100  , mod = 1e9 + 7 , inf = 1e17 , lg= 23 ; 
int b[maxn] , dp[maxn][lg+10] , t[maxn] , mark[maxn] , wp[maxn] , ed[maxn] , par[maxn][lg+10] , st[maxn] , en[maxn] ;
int dis[maxn] , dis2[maxn];vector<pii> G[maxn] ; 
int cnt =1 , mark2[maxn] ; 
void dfs(int v){
  mark[v] = 1;
  int m1 = 0,  m2 = 0 ;
  b[v] = inf ;vector <int> vec ;
  st[v] = cnt ;cnt++ ;
  for(int i =0 ; i < G[v].size() ; i++){
    int u = G[v][i].F , w = G[v][i].S ;
    if(mark[u] == 1)continue ;
    vec.pb(u);
    wp[u] = w ; 
    par[u][0] = v ; 
    dis[u] = dis[v]+ w ;
    dis2[u] = dis2[v] +1 ; 
    dfs(u) ;
    if(m1 == 0 || (b[u] + wp[u]) < (b[m1] + wp[m1])){
      swap(m1 , m2) ; 
      m1= u ;
    }else if(m2 == 0 || (b[u] + wp[u]) < (b[m2] + wp[m2])){
      m2 = u ;
    }
  }
  if(t[v] == 0){
  b[v] = b[m1] + wp[m1] ; 
  }else {
  b[v] = 0 ;
  m1 = m2 = -1;
  }
  for(int i =0 ; i < vec.size() ; i++){
    int u = vec[i]    ;
    int f = m1 ; 
    if(m1 == u)f =m2 ; 
    if(t[u] == 1){
      dp[u][0] = 0 ;
      continue ;
    }
    if(f==-1){
      dp[u][0] = wp[u] ;
      continue ;
    }
    dp[u][0] = min(wp[f] + wp[u] + b[f] , inf ) ;
 }
 en[v] = cnt ;cnt++ ;
}
vector <pii> vec ;

signed main(){
  ios_base::sync_with_stdio(false);cin.tie(0);
  int n , s , q , e ;
  cin >> n >> s>> q >> e ;
  for(int i =1; i <= n-1  ; i++){
    int v , u , w ;
    cin >> v >> u >> w ;
    G[v].pb({u,w}) ;
    G[u].pb({v,w}) ;vec.pb({v , u}) ;
  }
  for(int i =1 ; i <= s ; i++){
    int f ;cin >> f; 
    t[f] = 1; 
  }
  b[0] = inf ;
  dfs(e) ;
  for(int j = 1 ; j <= lg; j++){
    for(int i =1 ; i <= n ; i++){
      par[i][j] = par[par[i][j-1]][j-1] ;
      int x = par[i][j-1] ; 
      dp[i][j] = (((dis[i] - dis[x] + dp[x][j-1]) < dp[i][j-1]) ? (dis[i] - dis[x] + dp[x][j-1]) :  dp[i][j-1] );
    }
  }
  while(q--){
    int id , k ;
    cin >> id >> k ;
    int v = vec[id-1].F , u =vec[id-1].S ;
    if(dis[v] < dis[u])swap(v , u) ;
    if(!(st[k] >= st[v] && en[k] <= en[v])){
      cout << "escaped\n" ;
      continue ;
    }
    int ans = b[k]  ; 
    int x = dis2[k] - dis2[v] ; 
    int k1 = k ;
    for(int i = lg ; i >=0 ; i--){
      if(x>>i&1){
        if(ans > (dis[k1] - dis[k] + dp[k][i])){
          ans = (dis[k1] - dis[k] + dp[k][i]) ;
        }
        k = par[k][i] ; 
      }
    }
    if(ans >= inf){
      cout << "oo\n";
      continue ;
    }
    cout << ans << "\n" ;
  }
}

Compilation message (stderr)

valley.cpp: In function 'void dfs(long long int)':
valley.cpp:19:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |   for(int i =0 ; i < G[v].size() ; i++){
      |                  ~~^~~~~~~~~~~~~
valley.cpp:41:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   for(int i =0 ; i < vec.size() ; i++){
      |                  ~~^~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41