Submission #1096288

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096288		snowmel	Valley (BOI19_valley)	C++17	36 / 100	3016 ms	13280 KiB

valley

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int N, S, Q, H, C;
vector<pair<int,int>> QRS;
vector<tuple<int,int,ll>> edges;
vector<int> villages;
namespace sub12 {
vector<vector<int>> adj;
vector<int> is_village;
bool check() {
    return 1ll * N * Q <= int(1e6);
}
array<ll,3> dfs(int u, int p = -1) {
    array<ll,3> res;
    res[0] = res[1] = 0;
    res[2] = 1e18;
    if(u == H) res[0] = 1;
    if(is_village[u]) {
        res[1] = 1;
        res[2] = 0;
    }
    for(auto&& eid : adj[u]) {
        auto [ut, vt, w] = edges[eid];
        auto v = (ut != u ? ut : vt);
        if(v == p || w == -1) continue;
        auto t = dfs(v, u);
        res[0] |= t[0];
        res[1] |= t[1];
        if(t[1]) res[2] = min(res[2], t[2] + w);
    }
    return res;
}
void solve() {
    adj.assign(N, vector<int>());
    is_village.assign(N, 0);
    for(int i = 0; auto&& [x, y, z] : edges) {
        adj[x].emplace_back(i);
        adj[y].emplace_back(i);
        ++i;
    }
    for(auto&& v : villages) is_village[v] = 1;
    for(auto&& [x, y] : QRS) {
        auto t = get<2>(edges[x]);
        get<2>(edges[x]) = -1;
        auto tt = dfs(y);
        get<2>(edges[x]) = t;
        if(tt[0]) {
            cout << "escaped\n";
        } else if(tt[1]) {
            cout << tt[2] << "\n";
        } else {
            cout << "oo\n";
        }
    }
}
};
void solve() {
    cin >> N >> S >> Q >> H;
    --H;
    edges.resize(N - 1);
    QRS.resize(Q);
    villages.resize(S);
    for(auto& [u, v, w] : edges) {
        cin >> u >> v >> w;
        --u, --v;
    }
    for(auto& v : villages) {
        cin >> v;
        --v;
    }
    for(auto& [x, y] : QRS) {
        cin >> x >> y;
        --x, --y;
    }
    sub12::solve();
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    while(t--) solve();
}

Compilation message (stderr)

valley.cpp: In function 'void sub12::solve()':
valley.cpp:37:20: warning: range-based 'for' loops with initializer only available with '-std=c++2a' or '-std=gnu++2a'
   37 |     for(int i = 0; auto&& [x, y, z] : edges) {
      |                    ^~~~

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