Submission #1300575

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300575		hainam2k9	Valley (BOI19_valley)	C++20	23 / 100	123 ms	37720 KiB

valley

#include <bits/stdc++.h>
#define tt cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0)
#define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define db long double
#define sz(a) ((int)(a).size())
#define pb emplace_back
#define pf emplace_front
#define pob pop_back
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define ins emplace
#define mp make_pair
using namespace std;
const int MOD = 1e9+7, MAXN = 1e5+5;
const string NAME = "";
int n,m,q,root,depth[MAXN],par[MAXN][20],in[MAXN],out[MAXN],id=0;
ll dist[MAXN],mindist[MAXN],val[MAXN][20];
bool shop[MAXN];
pair<int,int> edge[MAXN];
vector<pair<int,int>> adj[MAXN];
void dfs(int u){
    if(shop[u]) mindist[u]=0;
    in[u]=++id;
    for(pair<int,int>& e : adj[u]){
        if(e.fi==par[u][0]) continue;
        depth[e.fi]=depth[u]+1, dist[e.fi]=dist[u]+e.se, par[e.fi][0]=u;
        for(int i = 1; i<=__lg(n); ++i)
            par[e.fi][i]=par[par[e.fi][i-1]][i-1];
        dfs(e.fi);
        mindist[u]=min(mindist[u],mindist[e.fi]+e.se);
    }
    val[u][0]=dist[u]-mindist[u];
    out[u]=id;
}
int main()
{
    tt;
    if(fopen((NAME + ".INP").c_str(), "r")) fo;
    cin >> n >> m >> q >> root;
    for(int i = 1; i<n; ++i){
        int x,y,z;
        cin >> x >> y >> z;
        adj[x].pb(y,z), adj[y].pb(x,z);
        edge[i]={x,y};
    }
    for(int i = 1; i<=m; ++i){
        int x;
        cin >> x;
        shop[x]=1;
    }
    memset(mindist,0x3f,sizeof(mindist));
    dfs(root);
    for(int i = 1; i<=__lg(n); ++i)
        for(int j = 1; j<=n; ++j)
            val[j][i]=max(val[j][i-1],val[par[j][i-1]][i-1]);
    while(q--){
        int x,u;
        cin >> x >> u;
        x=(depth[edge[x].fi]>depth[edge[x].se] ? edge[x].fi : edge[x].se);
        if(in[x]<=in[u]&&in[u]<=out[x]){
            if(mindist[x]>=1e18) cout << "oo\n";
            else{
                ll rs=1e18;
                for(int i = __lg(n); i>=0; --i)
                    if(depth[u]-(1<<i)+1>=depth[x]) rs=min(rs,dist[u]-val[u][i]), u=par[u][i];
                cout << rs << "\n";
            }
        }else cout << "escaped\n";
    }
}

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:3:19: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    3 | #define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
      |            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:44:45: note: in expansion of macro 'fo'
   44 |     if(fopen((NAME + ".INP").c_str(), "r")) fo;
      |                                             ^~
valley.cpp:3:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    3 | #define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
      |                                                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:44:45: note: in expansion of macro 'fo'
   44 |     if(fopen((NAME + ".INP").c_str(), "r")) fo;
      |                                             ^~

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