제출 #1169300

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1169300		sasde	Valley (BOI19_valley)	C++20	100 / 100	131 ms	58896 KiB

valley

#include<bits/stdc++.h>
#define int long long
#define str string
#define task "strdel"
#define ii pair<int,int>
#define iii pair<int,ii>
#define iv pair<ii,ii>
#define se second
#define fi first
#define ffi fi.fi
#define sfi se.fi
#define sse se.se
#define fse fi.se
#define lt(i, c, d) for(int i = c; i <= d; ++i)
#define fl(i, c, d) for(int i = d; i >= c; --i)
#define pb push_back
#define emb emplace_back
#define em emplace
using namespace std;
const int N=1e5+5,lg=20,mod=1e9+7;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int u,int v){
 return u+rd()%(v-u+1);
}
int h[N],up[N][lg+5];
int n,S,q,e,g[N],tin[N],tout[N],t;
long long k[N],f[N][lg+5],d[N];
vector<ii>a[N];
void dfs(int u,int cha){
  // cout <<u<<" ";
  tin[u]=++t;
  k[u]=1e18;
  if(g[u])k[u]=d[u];
  for(auto v:a[u]){
     if(v.fi==cha)continue;
     up[v.fi][0]=u;
     h[v.fi]=h[u]+1;
     d[v.fi]=d[u]+v.se;
     // cout<<u<<" "<<v.fi<<" "<<up[v.fi][0]<<'\n';
     dfs(v.fi,u);
     k[u]=min(k[u],k[v.fi]);

  }
  tout[u]=t;
}
long long lca(int u,int v,int goc){
  // cout<<ans<<" ";
  if(h[u]<h[v])swap(u,v);
  long long ans=k[u]-d[u];
  // cout << u<<" "<<v<<'\n'; 
  for(int j=lg;j>=0;--j){
    if(h[u]-h[v]>=(1<<j)){
      ans=min(ans,f[u][j]+d[goc]);
      // cout << u<<" "<<j <<" "<<f[u][j]<<" "<<d[u]<<'\n';
      u=up[u][j];
    }
  }
  return ans;
}
void dfs2(int u,int cha){
  for(ii v:a[u]){
    if(v.fi==cha)continue;
    // k[v.fi]=min(k[v.fi],k[u]);
  f[v.fi][0]=k[u]-2*d[u];
  // cout<<v.fi<<" "<<k[u]<<" "<<d[u]<<'\n';

    dfs2(v.fi,u);
  }
}
ii b[N];
void solve(){
  cin >>n >>S >>q >> e;
  // for(int i=1;i<=n;++i)for(int j=0;j<=lg;++j)f[i][j]=1e18;
  for(int i=1;i<n;++i){
    int u,v,w;
    cin >> u >> v >> w;
    a[u].emb(v,w);
    a[v].emb(u,w);
    b[i]={u,v};
  }
  while(S--){
    int u;
    cin >> u;
    g[u]=1;
  }
  dfs(e,-1);
  dfs2(e,-1);
  for(int j=1;j<=lg;++j){
    for(int i=1;i<=n;++i){
      up[i][j]=up[up[i][j-1]][j-1];
      f[i][j]=min(f[i][j-1],f[up[i][j-1]][j-1]);
    }
  }
  // f[e][0]=1e18;
  // for(int i=1;i<=n;++i)cout<<d[i]<<" "<<k[i]<<" "<<f[i][2]<<'\n'; ;
  while(q--){
    int i,y;
    cin >> i >> y;
    int u=y,v,goc=y;
    if(h[b[i].fi]>h[b[i].se])v=b[i].fi;
    else v=b[i].se;
    if(tin[v]<=tin[u]&&tout[u]<=tout[v]){
     long long ans=lca(u,v,goc);
     if(ans>=1e15)cout<<"oo";
     else{
      cout<<ans;
     }
    }
      else cout <<"escaped";
    if(q)cout<<'\n';
  }

}

main()
{
  srand(time(0));
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    if(fopen(task".inp","r")){
      freopen(task".inp","r",stdin);
      freopen(task".out","w",stdout);
    }
    int t=1;
 //   cin >> t;
while(t--){
    solve();
    if(t)cout<<'\n';
}

}

컴파일 시 표준 에러 (stderr) 메시지

valley.cpp:115:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  115 | main()
      | ^~~~
valley.cpp: In function 'int main()':
valley.cpp:122:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |       freopen(task".inp","r",stdin);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
valley.cpp:123:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |       freopen(task".out","w",stdout);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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