Submission #1275508

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275508		TVSown	Valley (BOI19_valley)	C++17	100 / 100	226 ms	26708 KiB

valley

#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define pi pair<int, int>
#define szz(s) int(s.size())
#define all(s) s.begin(), s.end()
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define REP(i, a, b) for(int i = a; i >= b; --i)
const int N = 1e5 + 5, MOD = 1e9 + 7;
int n, s, q, E, TIME;
int in[N], out[N], have[N];
long long d[N], ans[N];
vector<pi> e[N];
pi edge[N];
vector<pi> Q[N];
void pre(int u, int p){
    in[u] = ++TIME;

    for(auto [v, w] : e[u]){
        if(v == p) continue;
        d[v] = d[u] + w;
        pre(v, u);
    }
    out[u] = TIME;
}

int isChild(int u, int v){
    return in[u] <= in[v] && out[v] <= out[u];
}

long long st[4 * N], lz[4 * N];

void down(int id){
    st[2 * id] += lz[id];
    st[2 * id + 1] += lz[id];
    lz[2 * id] += lz[id];
    lz[2 * id + 1] += lz[id];
    lz[id] = 0;
}

void update(int id, int l, int r, int u, int v, long long x){
    if(l > v || r < u) return;

    if(u <= l && r <= v){
        st[id] += x;
        lz[id] += x;
        return;
    }
    down(id);
    int m = (l + r) / 2;
    update(2 * id, l, m, u, v, x);
    update(2 * id + 1, m + 1, r, u, v, x);
    st[id] = min(st[2 * id], st[2 * id + 1]);
}

long long get(int id, int l, int r, int u, int v){
    if(l > v || r < u) return 1e15;
    if(u <= l && r <= v) return st[id];
    down(id);
    int m = (l + r) / 2;
    return min(get(2 * id, l, m, u, v), get(2 * id + 1, m + 1, r, u, v));
}

void dfs(int u, int p, int S){
    update(1, 1, n, in[u], out[u], -S);
    update(1, 1, n, 1, in[u] - 1, S);
    update(1, 1, n, out[u] + 1, n, S);
//    cout << u << " " << Q[u].size() << "\n";
//    cout << "TEST: " << u << "\n";
//    FOR(u, 1, n){
//        cout << get(1, 1, n, in[u], in[u]) << " ";
//    }
//    cout << "\n";

    for(auto [id, i] : Q[u]){
        int x = edge[i].F, y = edge[i].S;
//        cout << u << " " << x << " " << y << "\n";
        if(isChild(y, u)){
            ans[id] = get(1, 1, n, in[y], out[y]);
        }else{
            ans[id] = min(get(1, 1, n, 1, in[y] - 1), get(1, 1, n, out[y] + 1, n));
        }
    }

    for(auto [v, w] : e[u]){
        if(v == p) continue;
        dfs(v, u, w);
    }

    update(1, 1, n, in[u], out[u], S);
    update(1, 1, n, 1, in[u] - 1, -S);
    update(1, 1, n, out[u] + 1, n, -S);
}

void solve(){
    cin >> n >> s >> q >> E;
    FOR(i, 1, n - 1){
        int u, v, w; cin >> u >> v >> w;
        e[u].pb({v, w});
        e[v].pb({u, w});
        edge[i] = {u, v};
    }
    FOR(i, 1, s){
        int c; cin >> c;
        have[c] = 1;
    }


    pre(1, 0);
    FOR(u, 1, n){
//        cout << have[u] << " " << in[u] << " " << d[u] << '\n';
        if(have[u]) update(1, 1, n, in[u], in[u], d[u]);
        else{
            update(1, 1, n, in[u], in[u], 1e15);
        }
    }

    FOR(id, 1, q){
        int i, R; cin >> i >> R;
        if(in[edge[i].F] > in[edge[i].S]) swap(edge[i].F, edge[i].S);
        int u = edge[i].F, v = edge[i].S;
//        cout << v << " " << R << " " << E << "\n";
        if(isChild(v, R) == isChild(v, E)){
            ans[id] = -1;
        }else{
            Q[R].pb({id, i});
//            cout << id << " " << R << "\n";
        }
    }

    dfs(1, 0, 0);

    FOR(id, 1, q){
        if(ans[id] == -1) cout << "escaped\n";
        else if(ans[id] <= 1e14) cout << ans[id] << "\n";
        else cout << "oo\n";
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
}

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