제출 #1219802

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219802		goulthen	Valley (BOI19_valley)	C++20	100 / 100	128 ms	23696 KiB

valley

//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define int long long
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define per(i, b, a) for (int i = b; i >= a; --i)
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
#define lsb(x) (x)&(-x)
 
void setIO(string name = "") {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    if (!name.empty()) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
}
ll fexp(ll a, ll b, ll m) {
    if (b == 0) return 1LL;
    ll p = a;
    ll ans = 1;
 
    while (b > 0) {
        if (b % 2 != 0) ans = (ans*p)%m;
        p = (p*p)%m;
        b >>= 1;
    }
    return ans;
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int MAXN = 1e5+10;
const int INF = 1e18+5;
const int MOD = 1e9+7;
vector<pii> g[MAXN];
int mk[MAXN], sz[MAXN], dp[MAXN], dep[MAXN], ti[MAXN], to[MAXN], n;
int p[MAXN], id[MAXN], tp[MAXN], st[4*MAXN];

void update(int idx, int val) {
    st[idx+=n] = val;
    for (idx /= 2; idx; idx /= 2) st[idx] = min(st[2*idx], st[2*idx+1]);
}

int query(int lo, int hi) {
    int ra = INF, rb = INF;
    for (lo += n, hi += n + 1; lo < hi; lo /= 2, hi /= 2) {
        if (lo & 1) ra = min(ra, st[lo++]);
        if (hi & 1) rb = min(rb, st[--hi]);
    }
    return min(ra, rb);
}
int tii = 0;
int dfs_sz(int u, int par) {
    sz[u] = 1;
    dp[u] = (mk[u]?dep[u]:INF);
    p[u] = par;
    ti[u] = ++tii;
    for (auto [v,w] : g[u]) {
        if (v == par) continue;
        dep[v] = dep[u] + w;
        p[v] = u;
        sz[u] += dfs_sz(v, u);
        dp[u] = min(dp[u], dp[v]);
    }
    to[u] = ++tii;
    return sz[u];
}

int ct = 1;

void dfs_hld(int cur, int par, int top) {
    id[cur] = ct++;
    tp[cur] = top;
    update(id[cur], dp[cur]);

    int h_chi = -1, h_sz = -1;
    for (auto &[chi,w] : g[cur]) {
        if (chi == par) continue;
        if (sz[chi] > h_sz) {
            h_sz = sz[chi];
            h_chi = chi;
        }
    }

    if (h_chi == -1) return;

    dfs_hld(h_chi, cur, top);

    for (auto &[chi,w] : g[cur]) {
        if (chi == par || chi == h_chi) continue;
        dfs_hld(chi, cur, chi);
    }
}

int path(int x, int y) {
    int ret = INF;
    while (tp[x] != tp[y]) {
        if (dep[tp[x]] < dep[tp[y]]) swap(x,y);
        ret = min(ret,query(id[tp[x]],id[x]));
        x = p[tp[x]];
    }

    if (dep[x] > dep[y]) swap(x,y);
    ret = min(ret, query(id[x],id[y]));
    return ret;
}

void solve() {
    int s,q,e;cin >> n >> s >> q >> e;
    vector<array<int,2>> edg;
    rep(i,1,n-1) {
        int u,v,w;cin >> u >> v >> w;
        g[u].pb({v,w});
        g[v].pb({u,w});
        edg.pb({u,v});
    }
    rep(i,1,s) {
        int u;cin >> u;
        mk[u] = 1;
    }
    dfs_sz(e,-1);
    rep(i,1,n) if (dp[i] != INF) dp[i] -= 2*dep[i];
    dfs_hld(e,-1,e);
    while (q--) {
        int id, u;cin >> id >> u;
        int cur = edg[id-1][0];
        if (dep[edg[id-1][1]] > dep[cur]) cur = edg[id-1][1];

        if (ti[u] < ti[cur] || to[u] > to[cur]) {
            cout << "escaped\n";
            continue;
        }
        int ans =path(u,cur);
        if (ans == INF) cout << "oo\n";
        else cout << ans + dep[u] << '\n';
    }
}

int32_t main() {
    setIO();
    int tt = 1;
    //cin >> tt;

    while (tt-- > 0) solve();
    
}

컴파일 시 표준 에러 (stderr) 메시지

valley.cpp: In function 'void setIO(std::string)':
valley.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         freopen((name + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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