제출 #1241139

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1241139		yassia	Valley (BOI19_valley)	C++20	100 / 100	114 ms	34232 KiB

valley

#ifndef local
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
#define int ll
using pii = pair<int, int>;
using pll = pair<ll,ll>;
using str = string;
using ld = long double;
using hash_map =gp_hash_table<int, int>;
using hash_set= gp_hash_table <int, null_type>;
auto sd = std::chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rnd(sd);
typedef tree<ll, null_type, less<>, rb_tree_tag,
        tree_order_statistics_node_update> ord_set;
const ll maxn = 3e5+8;
ll timer = 0;
ll hd[maxn];
ll pr[maxn];
ll tin[maxn];
ll tout[maxn];
ll sz[maxn];
ll d[1ll<<20];
ll dst[maxn];
pll mn[maxn];
ll wei[maxn];
bool is[maxn];
const ll inf1 = 1e14;
const ll inf = 1e18;
void upd(ll v, ll l, ll r, ll i, ll x){
    if (i==l && i+1==r){
        d[v] = x;
        return;
    }
    else if (i<l || r <= i){
        return;
    }
    upd(v*2, l, (l+r)/2, i ,x);
    upd(v*2+1, (l+r)/2, r, i, x);
    d[v] = min(d[v*2], d[v*2+1]);
}
ll sg(ll v, ll l, ll r, ll sl, ll sr){
    if (sl <= l && r <= sr){
        return d[v];
    }
    else if (sr <= l || r <= sl){
        return inf;
    }
    return min(sg(v*2, l, (l+r)/2, sl, sr),sg(v*2+1, (l+r)/2, r, sl ,sr));
}
void cnt_sz(ll v, vector<vector<ll>>&g, ll p){
    sz[v]++;
    pr[v] = p;
    for (auto u : g[v]){
        if (u != p){
            cnt_sz(u, g, v);
            sz[v] += sz[u];
        }
    }
}
void dfs(ll v, vector<vector<ll>>&g, ll p) {
    tin[v] = timer++;
    if (p != -1){
        dst[v] = dst[p]+wei[v];
    }
    ll x = -1;
    for (int i = 0; i < (g[v].size()); i++) {
        ll u = g[v][i];
        if (u != p && (x == -1 || sz[u] > sz[g[v][0]])) x = i, swap(g[v][0], g[v][i]);
    }

    for (int i = 0; i < (int)g[v].size(); i++) {
        ll u = g[v][i];
        if (u != p) {
            if (i == 0) hd[u] = hd[v];
            else hd[u] = u;
            dfs(u, g, v);
        }
    }
    tout[v] = timer++;
}
bool is_anc(ll v, ll u){
    if (tin[v]<= tin[u] && tout[v]>= tout[u]){
        return true;
    }return false;
}
void up(ll &ans, ll &u, ll &v){
    while (!is_anc(hd[u], v)){
        ans= min(ans,sg(1, 0, timer, tin[hd[u]], tin[u]+1));
        u = pr[hd[u]];
    }
}
ll get(ll u, ll v){
    ll ans = inf;
    up(ans, u, v);
    up(ans, v, u);
    if (!is_anc(u, v)){
        swap(u, v);
    }
    ans = min(ans, sg(1, 0, timer, tin[u], tin[v]+1));
    return ans;
}
void count_min(ll v, vector<vector<ll>>&g, ll p){
    if (is[v]){
        mn[v] = {0ll, v};
    }
    else mn[v] = {inf, 0};
    for (auto u : g[v]){
        if (u != p){
            count_min(u, g, v);
            mn[v] = min(mn[v], {mn[u].first+wei[u], mn[u].second});
        }
    }
}
void solve1() {
    ll n;
    cin >> n;
    ll s, q, e; cin >> s >> q >> e;
    for (auto &u : d) u = inf;
    vector<vector<ll>> g(n+1);
    vector<vector<ll>> edges;
    for (int i = 0; i < n-1; i++){
        ll u, v, w;
        cin>>u>>v>>w;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
        edges.push_back({u, v, w});
    }
    dst[0] = inf;
    hd[e] = e;
    cnt_sz(e, g, -1);
    for (auto &y: edges){
        ll u = y[0]; ll v = y[1]; ll w = y[2];
        if (u == pr[v]){
            wei[v] = w;
        }
        else wei[u] = w;
    }
    dfs(e, g, -1);

    for (int i =0; i < s; i++){
        ll v; cin >> v;
        is[v] = true;
    }
    count_min(e, g, -1);
    for (int i =0; i< n; i++){
        upd(1, 0, timer, tin[i+1], dst[mn[i+1].second]-2*dst[i+1]);
    }
    for (int i =0; i < q; i++){
        ll idx, v;
        cin >> idx >> v;
        auto B = edges[idx-1];
        ll a = B[0];
        ll b = B[1];
        if (pr[a]==b){
            swap(a, b);
        }
        if (!is_anc(a, v) || !is_anc(b, v)){
            cout<<"escaped\n";
            continue;
        }
        ll v1=  v;
        ll ans = dst[v1] + get(b, v);
        if (ans >= inf1){
            cout<<"oo\n";
        }
        else cout<<ans<<'\n';
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef local
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int t1 = 1;
    while (t1) solve1(), t1--;

#ifdef local
    printf_s("\n%.5f s", (double) clock() / CLOCKS_PER_SEC);
#endif
}

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