oj.uz

Submission #481250

# Submission time Handle Problem Language Result Execution time Memory
481250 2021-10-20T04:51:26 Z schiftyfive4 Valley (BOI19_valley) C++14
0 / 100
 198 ms 52584 KB 
#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

const int N = 100000;
const i64 inf = 1e18;
int n, s, q, E, t = 0;

vector<i64> in(N), out(N), shop(N), x(N, inf), dp(N), d(N);
vector<pair<int, int>> e;
vector<vector<pair<int, int>>> g(N);
vector<vector<i64>> go(N, vector<i64>(18)), mn(N, vector<i64>(18));

template<typename T, typename U>
std::ostream& operator<<(std::ostream& os, std::pair<T, U> v) {
    return os << '(' << v.first << ", " << v.second << ')';
}
template<typename T>
std::ostream& operator<<(std::ostream& os, std::set<T> s) {
    if (s.empty())
        return os << "{}";
    os << '{';
    for (auto it = s.begin(); it != prev(s.end()); it++) {
        os << *it << ", ";
    }
    return os << *(prev(s.end())) << '}';
}
template<typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> v) {
    if (v.empty())
        return os << "[]";
    os << '[';
    for (int i = 0; i < v.size() - 1; i++) {
        os << v[i] << ", ";
    }
    return os << v.back() << ']';
}

void dfs(int u, int p) {
    in[u] = t++;
    go[u][0] = p;
    if (shop[u]) {
        x[u] = d[u];
    }
    for (auto [v, w] : g[u])  { 
        if (v != p) {
            d[v] = d[u] + w;
            dfs(v, u);
            x[u] = min(x[u], x[v]);
        }
    }
    dp[u] = (x[u] == inf ? inf : x[u] - 2 * d[u]);
    out[u] = t++;
}

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> s >> q >> E;
    --E;

    for (int i = 0; i < n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        --u;
        --v;
        e.emplace_back(u, v);
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }

    for (int i = 0; i < s; i++) {
        int u;
        cin >> u;
        shop[u - 1] = 1;
    }

    dfs(E, E);

    for (int i = 0; i < n; i++) {
        mn[i][0] = min(dp[i], dp[go[i][0]]);
    }
    for (int b = 1; b < 18; b++) {
        for (int i = 0; i < n; i++) {
            go[i][b] = go[go[i][b - 1]][b - 1];
            mn[i][b] = min(mn[i][b - 1], mn[go[i][b - 1]][b - 1]);
        }
    }

    while (q--) {
        int i, r;
        cin >> i >> r;
        --i; --r;
        auto [u, v] = e[i];
        if (is_ancestor(u, v)) {
            swap(u, v);
        }
        if (!is_ancestor(u, r)) {
            cout << "escaped\n";
        } else {
            i64 best = inf, dd = d[r];
            for (int i = 17; i >= 0; i--) {
                if (is_ancestor(u, go[r][i])) {
                    best = min(best, mn[r][i]);
                    r = go[r][i];
                }
            }
            if (best == inf) {
                cout << "oo\n";
            } else {
                cout << dd + best << '\n';
            }
        }
    }

}

Compilation message

valley.cpp: In function 'void dfs(int, int)':
valley.cpp:46:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   46 |     for (auto [v, w] : g[u])  {
      |               ^
valley.cpp: In function 'int main()':
valley.cpp:100:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  100 |         auto [u, v] = e[i];
      |              ^

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 43460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 43460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 198 ms 52584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 43460 KB Output isn't correct
2 Halted 0 ms 0 KB -