Submission #496323

#	Time	Username	Problem	Language	Result	Execution time	Memory
496323		kingline	Valley (BOI19_valley)	C++17	59 / 100	3065 ms	14520 KiB

valley

/*#pragma GCC optimize("O3")
#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")*/
#include <bits/stdc++.h>
#define file(data) freopen(data".in", "r", stdin); freopen(data".out", "w", stdout);
#define pb push_back
#define all(data) data.begin(), data.end()
#define endl '\n'
#define ll long long
//#define int long long
#define pii pair < int, int >

using namespace std;

const int N = 2e5 + 5;

int n, s, q, e, a[N], b[N], w[N], block, deep[N], tin[N], tout[N];
bool shop[N], escape;
vector < pair < int, int > > g[N];
long long ans;

void found(int v, long long sum, int pr) {
    if(shop[v]) {
        ans = min(sum, ans);
    }
    if(v == e) {
        escape = 1;
        return;
    }
    for(int i = 0; i < g[v].size(); i++) {
        int to = g[v][i].first, len = g[v][i].second;
        if(to != pr) {
            if((a[block] == v && b[block] == to) || (a[block] == to && b[block] == v)) {
                continue;
            }
            found(to, sum + len, v);
        }
    }
}

int sz;
void dfs(int v, int pr) {
    tin[v] = ++sz;
    for(int i = 0; i < g[v].size(); i++) {
        int to = g[v][i].first;
        if(to != pr) {
            deep[to] = deep[v] + 1;
            dfs(to, v);
        }
    }
    tout[v] = sz;
}

bool upper(int aa, int bb) {
    return tin[aa] <= tin[bb] && tout[aa] >= tout[bb];
}

main() {
    //file("pieaters");
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> s >> q >> e;
    for(int i = 1; i < n; i++) {
        cin >> a[i] >> b[i] >> w[i];
        g[a[i]].pb({b[i], w[i]});
        g[b[i]].pb({a[i], w[i]});
    }
    for(int i = 1; i <= s; i++) {
        int x; cin >> x;
        shop[x] = 1;
    }
    if(s == n) {
        dfs(e, e);
        while(q--) {
            int start;
            cin >> block >> start;
            if(deep[a[block]] > deep[b[block]]) swap(a[block], b[block]);
            if(upper(b[block], start)) {
                cout << "0\n";
            } else {
                cout << "escaped\n";
            }
        }
        return 0;
    }
    while(q--) {
        int start;
        cin >> block >> start;
        escape = 0; ans = 1e14 + 1;
        found(start, 0, start);
        if(escape) {
            cout << "escaped\n";
        } else if(ans == 1e14 + 1) {
            cout << "oo\n";
        } else {
            cout << ans << endl;
        }
    }
}

Compilation message (stderr)

valley.cpp: In function 'void found(int, long long int, int)':
valley.cpp:32:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i = 0; i < g[v].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
valley.cpp: In function 'void dfs(int, int)':
valley.cpp:46:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i = 0; i < g[v].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
valley.cpp: At global scope:
valley.cpp:60:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   60 | main() {
      | ^~~~

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