Submission #354779

#	Time	Username	Problem	Language	Result	Execution time	Memory
354779		codebuster_10	Valley (BOI19_valley)	C++17	100 / 100	657 ms	82396 KiB

valley

#include <bits/stdc++.h>
 
using namespace std ;
 
#define i64 int64_t // typecast using i64(x)
#define int int64_t 
#define ld long double
#define f(i,a,b) for(int i=a; i<b; ++i)
#define endl '\n'
 
#define PQ priority_queue
#define LB lower_bound  
#define UB upper_bound
#define fr first
#define sc second
 
#define all(a) (a).begin(),(a).end()
#define allr(a) (a).rbegin(),(a).rend()
#define sz(x) ((int)(x).size())
 
//#ifndef ONLINE_JUDGE
template<typename T>
void __p(T a) {
  cout<<a; 
}
template<typename T, typename F>
void __p(pair<T, F> a) {
  cout<<"{";
  __p(a.first);
  cout<<",";
  __p(a.second);
  cout<<"}\n"; 
}
template<typename T>
void __p(std::vector<T> a) {
  cout<<"{";
  for(auto it=a.begin(); it<a.end(); it++)
    __p(*it),cout<<",}\n"[it+1==a.end()]; 
}
template<typename T, typename ...Arg>
void __p(T a1, Arg ...a) {
  __p(a1);
  __p(a...);
}
template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
  cout<<name<<" : ";
  __p(arg1);
  cout<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
  int bracket=0,i=0;
  for(;; i++)
    if(names[i]==','&&bracket==0)
      break;
    else if(names[i]=='(')
      bracket++;
    else if(names[i]==')')
      bracket--;
  const char *comma=names+i;
  cout.write(names,comma-names)<<" : ";
  __p(arg1);
  cout<<" | ";
  __f(comma+1,args...);
}
//#endif
 
void setIO(string s = "") {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
  cin.exceptions(cin.failbit); 
  if(sz(s)){
    freopen((s+".in").c_str(),"r",stdin);
    freopen((s+".out").c_str(),"w",stdout);
  }
}
const int INF = 1e16 ;
/**
 * Description: Euler Tour, LCA,  kth_ancestor
 * source: own
  * The root points to itself.
  * 0 based indexing
 * Time: O(N\log N) build, O(log N) LCA
 * Source: cp-algorithm, own
 * Verification: to be done
  * for kth_ancestor : https://cses.fi/problemset/result/1573131/
  * for lca : https://cses.fi/problemset/result/1573158/
 */
struct LCA {
  int N, timer = 0, LOG ; 
  vector< vector<int> > up, dis, val ;
  vector< vector< array<int,2> > > adj ;
  vector<int> tin, tout, depth, C, vec ;
 
  void init(int _N) { 
    N = _N ; LOG = log2(N) + 5 ; 
    adj.resize(N) ; 
    up.resize(N, vector<int> (LOG)) ;
    dis.resize(N, vector<int> (LOG)) ;
    val.resize(N, vector<int> (LOG, INF)) ;
    tin = tout = depth = vector<int> (N) ; 
    vec = vector<int> (N,INF) ; 
  }
 
  void ae(int x, int y,int w) { // add edge
    adj[x].push_back({y,w}), adj[y].push_back({x,w}); 
  }
 
  void dfs(int v, int p,int w){
    tin[v] = ++timer;
    up[v][0] = p ; dis[v][0] = w ;
    for(int i = 1; i < LOG; i++){
      up[v][i] = up[up[v][i-1]][i-1] ;
      dis[v][i] = dis[v][i-1] + dis[up[v][i-1]][i-1] ;
    } 
    for(auto [u,_w]:adj[v]) if(u != p){
      depth[u] = depth[v] + 1 ; dfs(u,v,_w) ;
    }
    tout[v] = ++timer ;
  }
 
  void gen(int R = 0) { 
    depth[R] = 0 ;
    dfs(R,R,0); 
    dfs2(R,R) ;
    f(i,0,N){
      val[i][0] = min(vec[i],dis[i][0] + vec[up[i][0]]) ;
    }
    f(j,1,LOG){
      f(i,0,N){
        val[i][j] = min(val[i][j-1],dis[i][j-1] + val[up[i][j-1]][j-1]) ;
      }
    }
    
    /*
    __f("vec",vec) ;
    f(i,0,N){
      f(j,0,LOG){
        __f("i,j,val[i][j]",i+1,j,val[i][j]) ;
      }
    }*/
  }
 
  void getC(vector<int> _C){
    C = _C ;
    for(auto i:C){
      vec[i] = 0 ;
    }
  }
 
  void dfs2(int i,int p){
    for(auto [j,w]:adj[i]) if(j!=p) {
      dfs2(j,i) ; vec[i] = min(vec[i],w + vec[j]) ;
    }
  }
 
  bool is_ancestor(int u, int v){
    return tin[u] <= tin[v] && tout[u] >= tout[v];
  }
 
  int lca(int u, int v){
    if( is_ancestor(u,v) )  return u;
    if( is_ancestor(v,u) )  return v;
    for(int i=LOG-1;i>=0;--i) {
      if( !is_ancestor(up[u][i],v) ){
        u = up[u][i] ;
      } 
    }
    return up[u][0];
  }
 
  int dist(int u, int v) {
    return depth[u] + depth[v] - 2 * depth[lca(u,v)]; 
  }
 
  int query(int i,int k){
    if(k == 0) return vec[i] ;
    int cur = dis[i][0] , ans = vec[i] ; i = up[i][0] ; k--;
    for(int j = LOG - 1; j >= 0; --j){
      if( (int(1) << j) <= k ){
        ans = min(ans, cur + val[i][j]) ;
        cur += dis[i][j] ;
        k -= (int(1) << j) ; 
        i = up[i][j] ; 
      }
    }
    assert(k == 0) ;
    ans = min(ans,cur + vec[i]) ;
    return ans ;
  }
};
signed main(){
  setIO() ; 
  int N, S, Q, E; cin >> N >> S >> Q >> E ; --E;
  vector<array<int,2> > edges ;
  LCA tree ; tree.init(N) ;
  f(i,0,N-1){
    int A, B, W; cin >> A >> B >> W ; --A,--B;
    edges.push_back({A,B}) ; tree.ae(A,B,W) ;
  }
  vector<int> C(S) ;
  f(i,0,S){ cin >> C[i] ; --C[i] ;}
 
  tree.getC(C) ;
  tree.gen(E) ;
  while(Q--){
    int I, R; cin >> I >> R ; --I,--R;
    int temp = tree.lca(edges[I][0],edges[I][1]) ;
    temp = (temp == edges[I][0] ? edges[I][1] : edges[I][0]) ;
    if( tree.lca(temp,R) != temp ){
      cout << "escaped\n" ; continue ;
    }
    int K = tree.depth[R] - tree.depth[temp]  ;
    int ans = tree.query(R,K) ;
    if(ans >= INF){
      cout << "oo\n" ;
    }else{
      cout << ans << endl ;
    }
  }
  
}

Compilation message (stderr)

valley.cpp: In function 'void setIO(std::string)':
valley.cpp:73:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   73 |     freopen((s+".in").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:74:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   74 |     freopen((s+".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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