Submission #1001329

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001329		ksu2009en	Valley (BOI19_valley)	C++17	100 / 100	411 ms	48256 KiB

valley

#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cstring>
#include <unordered_map>

using namespace std;
typedef long long ll;

ll dep[100007];
vector<pair<ll, ll>> d[100007];

ll t[400007], mod[400007], buildby[400007];
bool shop[100007];

ll n, s, q, e;


void build(ll v, ll l, ll r){
    if(l == r){
        t[v] = buildby[l];
        return;
    }
    
    ll mid = (l + r) >> 1;
    build(2 * v, l, mid);
    build(2 * v + 1, mid + 1, r);
    
    t[v] = min(t[2 * v], t[2 * v + 1]);
}

void push(ll v, ll l, ll r){
    if(mod[v] != 0 && l != r){
        t[2 * v] += mod[v];
        t[2 * v + 1] += mod[v];
        
        mod[2 * v] += mod[v];
        mod[2 * v + 1] += mod[v];
        
        mod[v] = 0;
    }
}

ll get(ll v, ll l, ll r, ll ql, ll qr){
    if(r < ql || qr < l)
        return (ll)(1e16);
    
    if(ql <= l && r <= qr)
        return t[v];
    
    ll mid = (l + r) >> 1;
    push(v, l, r);
    
    return min(get(2 * v, l, mid, ql, qr), get(2 * v + 1, mid + 1, r, ql, qr));
}

ll get1(ll v, ll l, ll r, ll pos){
    if(l == r)
        return t[v];
    
    ll mid = (l + r) >> 1;
    push(v, l, r);
    
    if(pos <= mid)
        return get1(2 * v, l, mid, pos);
    return get1(2 * v + 1, mid + 1, r, pos);
}

void update(ll v, ll l, ll r, ll ql, ll qr, ll val){
    if(r < ql || qr < l)
        return;
    
    if(ql <= l && r <= qr){
        t[v] += val;
        mod[v] += val;
        
        return;
    }
    
    ll mid = (l + r) >> 1;
    push(v, l, r);
    
    update(2 * v, l, mid, ql, qr, val);
    update(2 * v + 1, mid + 1, r, ql, qr, val);
    
    t[v] = min(t[2 * v], t[2 * v + 1]);
}

ll time_in[100007], time_out[100007];
ll step = 0;

void dfs(ll v, ll par){
    time_in[v] = ++step;
    
    for(auto i: d[v]){
        if(i.first != par){
            dep[i.first] = dep[v] + i.second;
            dfs(i.first, v);
        }
    }
    
    time_out[v] = step;
}

bool ispar(ll a, ll b){
    return time_in[a] <= time_in[b] && time_in[b] <= time_out[a];
}

vector<pair<ll, ll>> quer[100007];
vector<pair<ll, ll>> edges;

string ans[100007];

void dfs2(ll v, ll par){
    for(auto p: quer[v]){
        pair<ll, ll> i = edges[p.first - 1];
        
        if(ispar(i.second, v)){
            update(1, 1, n, 1, n, (ll)(1e16));
            update(1, 1, n, time_in[i.second], time_out[i.second], -(ll)(1e16));
        }
        else{
            update(1, 1, n, time_in[i.second], time_out[i.second], (ll)(1e16));
        }
        
//        for(int j = 1; j <= n; j++)
//            cout << get1(1, 1, n, time_in[j]) << ' ';
//        cout << endl;
        
        ll val = get1(1, 1, n, time_in[e]);
        if(val < (ll)(1e16)){
            ans[p.second] = "escaped";
        }
        else{
            ll h = get(1, 1, n, 1, n);
            
            if(h < (ll)(1e16))
                ans[p.second] = to_string(h);
            else
                ans[p.second] = "oo";
        }
        
        if(ispar(i.second, v)){
            update(1, 1, n, 1, n, -(ll)(1e16));
            update(1, 1, n, time_in[i.second], time_out[i.second], (ll)(1e16));
        }
        else{
            update(1, 1, n, time_in[i.second], time_out[i.second], -(ll)(1e16));
        }
    }
    
    for(auto i: d[v]){
        if(i.first != par){
            update(1, 1, n, 1, n, i.second);
            update(1, 1, n, time_in[i.first], time_out[i.first], -2 * i.second);

            dfs2(i.first, v);
            
            update(1, 1, n, 1, n, -i.second);
            update(1, 1, n, time_in[i.first], time_out[i.first], 2 * i.second);
        }
    }
}

int main(){
    cin >> n >> s >> q >> e;
    
    for(int i = 0; i < n - 1; i++){
        ll a, b, c;
        cin >> a >> b >> c;
        
        edges.push_back({a, b});
        
        d[a].push_back({b, c});
        d[b].push_back({a, c});
    }
    
    for(int i = 0; i < s; i++){
        ll c;
        cin >> c;
        
        shop[c] = true;
    }
    
    dfs(1, -1);
    // fill in buildby
    
    for(int i = 1; i <= n; i++){
        if(!shop[i] && i != e){
            buildby[time_in[i]] = dep[i] + (ll)(1e16);
            continue;
        }
        
        buildby[time_in[i]] = dep[i];
    }

    build(1, 1, n);
    
    for(auto &i: edges){
        if(dep[i.first] > dep[i.second])
            swap(i.first, i.second);
    }
    
    for(int i = 0; i < q; i++){
        ll e, v;
        cin >> e >> v;
        
        quer[v].push_back({e, i});
    }
    
    dfs2(1, -1);
    
    for(int i = 0; i < q; i++)
        cout << ans[i] << endl;
    
    return 0;
}

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