Submission #1275902

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275902		tu2108	Valley (BOI19_valley)	C++20	100 / 100	326 ms	28252 KiB

valley

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define faster ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fi first
#define se second
#define pb push_back
#define getbit(x , i) ((x >> i) & 1)
typedef pair<int , int> pii;

const int inf = 1e18;
const int mod = 1e9 + 7;
const int maxn = 1e5;

int n , s , root , q , tin = 0;
vector<pii> adj[maxn + 5];
vector<int> qr1[maxn + 5];
int d[maxn + 5] , in[maxn + 5] , out[maxn + 5] , st[4 * maxn + 5] , lazy[4 * maxn + 5] , ans[maxn + 5];
pii qr[maxn + 5];
bool check[maxn + 5];

struct edge{
    int u , v , w;
};
edge e[maxn + 5];

void dfs(int u){
    in[u] = ++tin;

    for(auto v : adj[u]){
        if(in[v.fi]) continue;
        d[v.fi] = d[u] + v.se;

        dfs(v.fi);
    }
    out[u] = tin;
}

void add(int id , int val){
    st[id] += val;
    lazy[id] += val;
}

void down(int id){
    add(id * 2 , lazy[id]);
    add(id * 2 + 1 , lazy[id]);
    lazy[id] = 0;
}

void update(int id , int l , int r , int u , int v , int val){
    if(v < l || r < u) return;
    if(u <= l && r <= v){
        add(id , val);
        return;
    }
    if(lazy[id] != 0) down(id);

    int mid = (l + r) >> 1;
    update(id * 2 , l , mid , u , v , val);
    update(id * 2 + 1 , mid + 1 , r , u , v , val);

    st[id] = min(st[id * 2] , st[id * 2 + 1]);
}

int get(int id , int l , int r , int u , int v){
    if(v < l || r < u) return inf;
    if(u <= l && r <= v) return st[id];
    if(lazy[id] != 0) down(id);

    int mid = (l + r) >> 1;
    int getl = get(id * 2 , l , mid , u , v);
    int getr = get(id * 2 + 1 , mid + 1 , r , u , v);
    return min(getl , getr);
}

void dfs1(int u){
    for(auto i : qr1[u]){
        int id = qr[i].fi;
        ans[i] = get(1 , 1 , n , in[e[id].v] , out[e[id].v]);
    }

    for(auto v : adj[u]){
        if(d[v.fi] < d[u]) continue;

        update(1 , 1 , n , 1 , in[v.fi] - 1 , v.se);
        update(1 , 1 , n , out[v.fi] + 1 , n , v.se);
        update(1 , 1 , n , in[v.fi] , out[v.fi] , -v.se);

        dfs1(v.fi);

        update(1 , 1 , n , 1 , in[v.fi] - 1 , -v.se);
        update(1 , 1 , n , out[v.fi] + 1 , n , -v.se);
        update(1 , 1 , n , in[v.fi] , out[v.fi] , v.se);
    }
}

main()
{
    faster
    cin >> n >> s >> q >> root;
    for(int i = 1 ; i < n ; ++i){
        cin >> e[i].u >> e[i].v >> e[i].w;
        adj[e[i].u].pb({e[i].v , e[i].w});
        adj[e[i].v].pb({e[i].u , e[i].w});
    }
    for(int i = 1 ; i <= s ; ++i){
        int u;
        cin >> u;
        check[u] = 1;
    }

    dfs(root);

    for(int i = 1 ; i < n ; ++i){
        if(d[e[i].u] > d[e[i].v]) swap(e[i].u , e[i].v);
    }

    for(int i = 1 ; i <= n ; ++i){
        int val = d[i];
        if(!check[i]) val = inf;
        update(1 , 1 , n , in[i] , in[i] , val);
    }

    for(int i = 1 ; i <= q ; ++i){
        cin >> qr[i].fi >> qr[i].se;
        int id = qr[i].fi , x = qr[i].se;

        if(in[e[id].v] <= in[x] && in[x] <= out[e[id].v]) qr1[x].pb(i);
        else ans[i] = -1;
    }

    dfs1(root);

    for(int i = 1 ; i <= q ; ++i){
        if(ans[i] == -1) cout << "escaped" << '\n';
        else if(ans[i] >= 1e17) cout << "oo" << '\n';
        else cout << ans[i] << '\n';
    }
}

Compilation message (stderr)

valley.cpp:97:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   97 | main()
      | ^~~~

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