Submission #1282131

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282131		quan606303	Valley (BOI19_valley)	C++20	100 / 100	148 ms	45788 KiB

valley

/*
 * @Author: RMQuan 
 * @Date: 2025-10-22 18:51:18 
 * @Last Modified by: RMQuan
 * @Last Modified time: 2025-10-22 21:48:17
 */
/*idea : 



*/
#include <bits/stdc++.h>
bool M1;
#define int long long
#define ll long long
#define INTMAX INT_MAX
#define INTMIN INT_MIN
#define LONGMAX LLONG_MAX
#define LONGMIN LLONG_MIN
#define fi first
#define se second
#define memfull(a,b) memset(a,b,sizeof(a));
#define endl '\n'
#define TASK "TEST"
#define file() if (fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin); freopen(TASK".out","w",stdout);}
using namespace std;
const int MOD=1e9+7;
const int maxn=1e5+7;
const int inf=4e18;
const int LOG=17;
bool is_shop[maxn];
int N,Q,C,E;
vector<pair<int,int> > adj[maxn];
pair<int,int> edge[maxn];
int up[maxn][LOG+1],dp[maxn],h[maxn],mn[maxn][LOG+1],depth[maxn];
void pre_dfs_dp(int u,int p)
{
    
    if (is_shop[u])dp[u]=depth[u];
    else dp[u]=inf;
    for (auto v:adj[u])
    {
        if (v.fi==p)continue;
        h[v.fi]=h[u]+1;
        depth[v.fi]=depth[u]+v.se;
        pre_dfs_dp(v.fi,u);
        dp[u]=min(dp[u],dp[v.fi]);
    }
}
void dfs_lca(int u,int p)
{
    for(auto v:adj[u])
    {
        if (v.fi==p)continue;
        up[v.fi][0]=u;
        mn[v.fi][0]=min(dp[u]-2*depth[u],dp[v.fi]-2*depth[v.fi]);
        for (int i=1;i<=LOG;i++)
        {
            up[v.fi][i]=up[up[v.fi][i-1]][i-1];
            mn[v.fi][i]=min(mn[v.fi][i-1],mn[up[v.fi][i-1]][i-1]);
        }
        dfs_lca(v.fi,u);
    }
}
int lca(int u,int v)
{
    if (h[u]<h[v])swap(u,v);
    for (int i=LOG;i>=0;i--)if (h[up[u][i]]>=h[v])u=up[u][i];
    if (u==v)return u;
    for (int i=LOG;i>=0;i--)
    {
        if (up[u][i]!=up[v][i])
        {
            u=up[u][i];
            v=up[v][i];
        }
    }
    return up[u][0];
}
int dist(int u,int v)
{
    return h[u]+h[v]-2*h[lca(u,v)];
}
int get_min(int u,int LCA)
{
    if (u==LCA)
    {
        return dp[u]-2*depth[u];
    }
    int ans=inf;
    int diff=h[u]-h[LCA];
    for (int i=LOG;i>=0;i--)if (diff&(1<<i)){ans=min(ans,mn[u][i]);u=up[u][i];}
    return ans;
}
void solve()
{
    cin>>N>>C>>Q>>E;
    for (int i=1;i<N;i++)
    {
        int x,y,w;
        cin>>x>>y>>w;
        adj[x].push_back({y,w});
        adj[y].push_back({x,w});
        edge[i]={x,y};
    }
    for (int i=1;i<=C;i++)
    {
        int x;
        cin>>x;
        is_shop[x]=true;
    }
    h[0]=-1;
    pre_dfs_dp(E,0);
    dfs_lca(E,0);
    for (int i=1;i<N;i++)if (h[edge[i].fi]>h[edge[i].se])swap(edge[i].fi,edge[i].se);
    while (Q--)
    {
        int block,pos,u,v;
        cin>>block>>pos;
        tie(u,v)=edge[block];
        if (h[u]+1+dist(v,pos)!=h[pos])cout<<"escaped"<<endl;
        else 
        {
            int ans=depth[pos]+get_min(pos,v);
            if (ans>=1e18)cout<<"oo"<<endl;
            else cout<<ans<<endl;
        }
    }

}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    file();
    solve();
    bool M2;
    cerr<<"-------------------------------------------------"<<endl;
    cerr<<"Time : "<<clock()<<" ms"<<endl;
    cerr<<"Memory : "<<abs(&M2-&M1)/1024/1024<<" MB"<<endl;
    cerr<<"-------------------------------------------------"<<endl;
    return 0;
}

Compilation message (stderr)

valley.cpp: In function 'int32_t main()':
valley.cpp:25:50: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 | #define file() if (fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin); freopen(TASK".out","w",stdout);}
      |                                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
valley.cpp:136:5: note: in expansion of macro 'file'
  136 |     file();
      |     ^~~~
valley.cpp:25:81: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 | #define file() if (fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin); freopen(TASK".out","w",stdout);}
      |                                                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:136:5: note: in expansion of macro 'file'
  136 |     file();
      |     ^~~~

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