Submission #1104686

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104686		huyngodzz	Valley (BOI19_valley)	C++14	100 / 100	146 ms	65052 KiB

valley

    ///huynhocute123///
#include<bits/stdc++.h>
using namespace std;
#define S second
#define F first
#define pii pair<long long,long long>
#define piii pair<int,pair<int,int>>
#define pb push_back
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define REP(i, a, b) for(int i = b; i >= a; --i)
#define ALL(v) v.begin(),v.end()
#define inp(name) if(fopen(name, "r")) freopen(name, "r", stdin);
#define out(name) if(fopen(name, "w")) freopen(name, "w", stdout);
//random_device rd;
//mt19937 rng(rd());
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("popcnt")
//#define int long long
const int maxN =  2 * 1e5 + 9;
const int  modd = 1e9 + 7;
const int base = 2309;
const long long MAX = 1e18+9;
const double pi = 3.14159265358979323846;
const double rad = 3.14159265358979323846 /180;
void minimize(long long &u, long long v){
    if(v < u) u = v;
}
void maximize(int &u, int v){
    if(v > u) u = v;
}
int n, k, t, m, res, q, a[maxN], root, shop[maxN], dep[maxN], in[maxN], out[maxN], cnt, Numshop;
long long dis[maxN], f[maxN];
int l, r;
pii edge[maxN], T[maxN][21];
bool isshop[maxN];
vector<pii> e[maxN];
void dfs(int u, int p){
    in[u] =++cnt;
    if(isshop[u]){
        shop[u]=1;
        f[u] = dis[u];
    }
    for(auto [x, w] : e[u]){
        if(x == p)continue;
        T[x][0].F = u;
        dis[x] =dis[u] + w;
        dep[x] =dep[u] +1;
        dfs(x, u);
        minimize(f[u], f[x]);
        shop[u] +=shop[x];
    }
    out[u]= cnt;
}
bool ischild(int u ,int v){
    /// u is partent v
    return ( in[u] <= in[v] && out[u] >= out[v]);
}
void build(){
    for(int i =1; i <= n ;i++)T[i][0].S =f[i];
    for(int i= 1;i <= 20; i++){
        for(int u= 1;u <= n ;u++){
            T[u][i].F = T[T[u][i-1].F][i-1].F;
            T[u][i].S = min(T[u][i-1].S , T[T[u][i-1].F][i-1].S);
        }

    }
}
long long jump(int u ,int v){
    long long ans = MAX;
    for(int i = 20 ;i >= 0 ;i--){
        if(dep[u] - dep[v] + 1 >= ( 1 << i)){
            minimize(ans, T[u][i].S);
            u = T[u][i].F;
        }

    }
    return ans;
}
void solve(){
    cin >> n >> Numshop >> q >> root;
    for(int i =1;i < n ; i++){
        int x;cin >> l >> r >> x;
        e[l].pb({r, x});
        e[r].pb({l ,x});
        edge[i]= {l ,r};
    }
    for(int i =1;i <= n ;i++)f[i]= MAX;
    for(int i=1;i <= Numshop;i++){
        int x;cin >> x;
        isshop[x]= 1;
    }
    dfs(root ,0);
//    for(int i =1;i <= n ;i++)cout << f[i] << " ";
    for(int i =1;i <= n ;i++)f[i]-= 2 * dis[i];
    build();
    for(int ix =1; ix <= q; ix++){
        int id , x;
        cin >> id >> x;
        int u = edge[id].F , v= edge[id].S;
        int nod = (dep[u] > dep[v] ? u : v);
        if(ischild(nod, x)){
            if(shop[nod] == 0) cout << "oo" << '\n';
            else cout << dis[x] + jump(x, nod) << '\n';
        }else{
            cout << "escaped" << '\n';
        }


    }

}
signed main(){
//    freopen("name.inp","r",stdin);
//    freopen("name.out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    inp("task.inp");
    t = 1;
   // cin >> t;
    while( t-- )solve();

}

Compilation message (stderr)

valley.cpp: In function 'void dfs(int, int)':
valley.cpp:44:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   44 |     for(auto [x, w] : e[u]){
      |              ^
valley.cpp: In function 'int main()':
valley.cpp:12:47: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define inp(name) if(fopen(name, "r")) freopen(name, "r", stdin);
      |                                        ~~~~~~~^~~~~~~~~~~~~~~~~~
valley.cpp:118:5: note: in expansion of macro 'inp'
  118 |     inp("task.inp");
      |     ^~~

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