제출 #698862

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
698862		nguyentunglam	Valley (BOI19_valley)	C++17	100 / 100	258 ms	39268 KiB

valley

#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
using namespace std;
const int N = 1e5 + 10;
int par[20][N];
long long f[20][N], d[N];
int st[N], ed[N], cnt;
pair<int, int> edge[N];
vector<pair<int, int> > adj[N];
void dfs(int u) {
    st[u] = ++cnt;
    for(auto &[v, w] : adj[u]) if (v != par[0][u]) {
        par[0][v] = u; d[v] = d[u] + w;
        dfs(v);
        f[0][u] = min(f[0][u], f[0][v] + w);
    }
    ed[u] = cnt;
}
void scan(int u) {
    for(int j = 1; j <= 17; j++) {
        int anc = par[j - 1][u];
        par[j][u] = par[j - 1][anc];
        f[j][u] = min(f[j - 1][u], f[j - 1][anc] + d[u] - d[anc]);
    }
    for(auto &[v, w] : adj[u]) if (v != par[0][u]) scan(v);
}
bool inside(int p, int u) {
    return (st[p] <= st[u] && st[u] <= ed[p]);
}
int main() {
    #define task ""
    cin.tie(0) -> sync_with_stdio(0);
    if (fopen ("task.inp", "r")) {
        freopen ("task.inp", "r", stdin);
        freopen ("task.out", "w", stdout);
    }
    if (fopen (task".inp", "r")) {
        freopen (task".inp", "r", stdin);
        freopen (task".out", "w", stdout);
    }
    int n, s, q, e; cin >> n >> s >> q >> e;
    for(int i = 1; i < n; i++) {
        int a, b, w; cin >> a >> b >> w;
        adj[a].emplace_back(b, w);
        adj[b].emplace_back(a, w);
        edge[i] = make_pair(a, b);
    }
    memset(f, 127, sizeof(f));
    while (s--) {
        int c; cin >> c; f[0][c] = 0;
    }
    dfs(e);
    scan(e);
    while (q--) {
        int i, r; cin >> i >> r;
        auto &[u, v] = edge[i];
        if (st[u] > st[v]) swap(u, v);
        if (inside(v, r)) {
            int ver = r;
            long long ans = 1e18;
            for(int j = 17; j >= 0; j--) if (inside(u, par[j][ver])) {
                ans = min(ans, d[r] - d[ver] + f[j][ver]);
                ver = par[j][ver];
            }
            if (ans == 1e18) cout << "oo";
            else cout << ans;
            cout << endl;
        }
        else cout << "escaped\n";
    }
}

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

valley.cpp: In function 'int main()':
valley.cpp:37:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen ("task.inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:38:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen ("task.out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:41:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen (task".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:42:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         freopen (task".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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