Submission #496546

#	Time	Username	Problem	Language	Result	Execution time	Memory
496546		kingline	Valley (BOI19_valley)	C++17	0 / 100	231 ms	61812 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 < ll, ll >

using namespace std;

const int N = 2e5 + 5;
const int lg = 21;

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

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, len = g[v][i].second;
        if(to != pr) {
            deep[to] = deep[v] + 1;
            dist[to] = dist[v] + len;
            dfs(to, v);
        }
    }
    tout[v] = sz;
}

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

vector < pii > gg[N];

int up[N][lg], mn[N][lg];
void calc_lca(int v, int pr) {
    up[v][0] = pr;
    for(int i = 1; i < lg; i++) {
        up[v][i] = up[up[v][i - 1]][i - 1];
        mn[v][i] = min(mn[v][i - 1], mn[up[v][i - 1]][i - 1]);
    }
    for(int i = 0; i < gg[v].size(); i++) {
        int to = gg[v][i].first, len = gg[v][i].second;
        if(to != pr) {
            mn[to][0] = len;
            calc_lca(to, v);
        }
    }
}

void build() {
    for(int i = 1; i < n; i++) {
        gg[a[i]].pb({b[i], min(-dist[a[i]] + dp[a[i]], -dist[b[i]] + dp[b[i]])});
        swap(a[i], b[i]);
        gg[a[i]].pb({b[i], min(-dist[a[i]] + dp[a[i]], -dist[b[i]] + dp[b[i]])});
    }
    calc_lca(e, e);
}

int lca(int aa, int bb) {
    if(upper(aa, bb)) return aa;
    if(upper(bb, aa)) return bb;
    for(int i = lg - 1; i >= 0; i--) {
        if(up[aa][i] == 0) continue;
        if(!upper(up[aa][i], bb)) {
            aa = up[aa][i];
        }
    }
    return up[aa][0];
}

int got(int s, int t) {
    int res = 1e15, la = s;
    for(int j = lg - 1; j >= 0 && la != t; j--) {
        if(up[t][j] == 0) continue;
        if(!upper(up[t][j], la)) {
            res = min(res, mn[t][j]);
            t = up[t][j];
        }
    }
    if(la != t) res = min(res, mn[t][0]);
    return res;
}

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]});
        dp[i] = 1e15;
    }
    dp[n] = 1e15;
    dfs(e, e);
    set < pii > st;
    for(int i = 1; i <= s; i++) {
        int x; cin >> x;
        shop[x] = 1;
        st.insert({0, x});
        dp[x] = 0;
    }
    while(st.size()) {
        int now = (*st.begin()).second;
        st.erase(*st.begin());
        for(int i = 0; i < g[now].size(); i++) {
            int to = g[now][i].first, len = g[now][i].second;
            if(deep[to] < deep[now] && dp[to] > dp[now] + len) {
                st.erase({dp[to], to});
                dp[to] = dp[now] + len;
                st.insert({dp[to], to});
            }
        }
    }
    build();
    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 << "escaped\n";
        } else if(dp[b[block]] >= 1e15){
            cout << "oo\n";
        } else {
            int gt = got(b[block], start);
            cout << gt + dist[start] << endl;
        }
    }
}

Compilation message (stderr)

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

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