제출 #254954

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
254954		jovan_b	Valley (BOI19_valley)	C++17	100 / 100	346 ms	29768 KiB

valley

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

ll res[100005];
vector <pair <int, int>> graf[100005];
ll depth[100005];
pair <ll, int> niz[100005];

int e;

const ll INF = 1000000000000000LL;

struct segment{
    ll lazy, res;
} seg[400005];

int tajm;
int in[100005];
int out[100005];
bool jeste[100005];
vector <pair <int, int>> kv[100005];
int n;

void init(int node, int l, int r){
    if(l == r){
        if(niz[l].second == 1) seg[node].res = niz[l].first;
        else seg[node].res = INF;
        return;
    }
    int mid = (l+r)/2;
    init(node*2, l, mid);
    init(node*2+1, mid+1, r);
    seg[node].res = min(seg[node*2].res, seg[node*2+1].res);
}

void dfs1(int v, int parent, int kolko){
    depth[v] = depth[parent] + kolko;
    in[v] = ++tajm;
    niz[in[v]] = {depth[v], jeste[v]};
    for(auto c : graf[v]){
        if(c.first == parent) continue;
        dfs1(c.first, v, c.second);
    }
    out[v] = tajm;
}

void propagate(int node, int l, int r){
    seg[node].res += seg[node].lazy;
    if(l == r){
        seg[node].lazy = 0;
        return;
    }
    seg[node*2].lazy += seg[node].lazy;
    seg[node*2+1].lazy += seg[node].lazy;
    seg[node].lazy = 0;
}

void upd(int node, int l, int r, int tl, int tr, int val){
    if(tl > tr) return;
    propagate(node, l, r);
    if(tl > r || l > tr) return;
    if(tl <= l && r <= tr){
        seg[node].lazy += val;
        propagate(node, l, r);
        return;
    }
    int mid = (l+r)/2;
    upd(node*2, l, mid, tl, tr, val);
    upd(node*2+1, mid+1, r, tl, tr, val);
    seg[node].res = min(seg[node*2].res, seg[node*2+1].res);
}


ll query(int node, int l, int r, int tl, int tr){
    if(tl > tr) return INF;
    propagate(node, l, r);
    if(tl > r || l > tr) return INF;
    if(tl <= l && r <= tr) return seg[node].res;
    int mid = (l+r)/2;
    return min(query(node*2, l, mid, tl, tr), query(node*2+1, mid+1, r, tl, tr));
}

struct edge{
    int a, b, c;
} grana[100005];

bool is_parent(int a, int b){
    return in[a] <= in[b] && out[b] <= out[a];
}

void dfs(int v, int parent, int kolko){
    upd(1, 1, n, 1, n, kolko);
    upd(1, 1, n, in[v], out[v], -2*kolko);
    for(auto c : kv[v]){
        int edg = c.first;
        if(in[grana[edg].a] > in[grana[edg].b]) swap(grana[edg].a, grana[edg].b);
        int b = grana[edg].b;
        if(is_parent(b, v)) res[c.second] = query(1, 1, n, in[b], out[b]);
        else res[c.second] = min(query(1, 1, n, 1, in[b]-1), query(1, 1, n, out[b]+1, n));
    }
    for(auto c : graf[v]){
        if(c.first == parent) continue;
        dfs(c.first, v, c.second);
    }
    upd(1, 1, n, 1, n, -kolko);
    upd(1, 1, n, in[v], out[v], 2*kolko);
}

bool check(int x, int edg){
    if(in[grana[edg].a] > in[grana[edg].b]) swap(grana[edg].a, grana[edg].b);
    int b = grana[edg].b;
    if(is_parent(b, e)) return is_parent(b, x);
    else return !is_parent(b, x);
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int s, q;
    cin >> n >> s >> q >> e;
    for(int i=1; i<n; i++){
        int a, b, c;
        cin >> a >> b >> c;
        graf[a].push_back({b, c});
        graf[b].push_back({a, c});
        grana[i] = {a, b, c};
    }
    for(int j=1; j<=s; j++){
        int x;
        cin >> x;
        jeste[x] = 1;
    }
    dfs1(1, 0, 0);
    init(1, 1, n);
    for(int j=1; j<=q; j++){
        int a, b;
        cin >> b >> a;
        if(check(a, b)){
            res[j] = -1;
            continue;
        }
        res[j] = INF;
        kv[a].push_back({b, j});
    }
    dfs(1, 0, 0);
    for(int j=1; j<=q; j++){
        if(res[j] == -1) cout << "escaped\n";
        else if(res[j] > INF/10) cout << "oo\n";
        else cout << res[j] << "\n";
    }
    return 0;
}

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