oj.uz

Submission #496456

# Submission time Handle Problem Language Result Execution time Memory
496456 2021-12-21T08:29:22 Z kingline Valley (BOI19_valley) C++17
23 / 100
 131 ms 15752 KB 
/*#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], d[N];
bool shop[N], escape;
vector < pair < int, int > > 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;
        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];
}

int t[4 * N];
void update(int v, int l, int r, int pos, int val) {
    if(l == r) {
        t[v] += val;
        return;
    }
    int md = (l + r) / 2;
    if(pos <= md) {
        update(v * 2, l, md, pos, val);
    } else {
        update(v * 2 + 1, md + 1, r, pos, val);
    }
    t[v] = t[v * 2] + t[v * 2 + 1];
}

int get(int v, int l, int r, int tl, int tr) {
    if(tl <= l && r <= tr) {
        return t[v];
    }
    if(r < tl || tr < l) return 0;
    int md = (l + r) / 2;
    return get(v * 2, l, md, tl, tr) + get(v * 2 + 1, md + 1, r, tl, tr);
}

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]});
    }
    dfs(e, e);
    for(int i = 1; i <= s; i++) {
        int x; cin >> x;
        shop[x] = 1;
        update(1, 1, n, tin[x], 1);
    }
    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(get(1, 1, n, tin[b[block]], tout[b[block]]) == 0){
            cout << "oo\n";
        } else if(shop[start]){
            cout << "0\n";
        } else {
            set < pii > st;
            set < int > path;
            d[start] = 0;
            st.insert({0, start});
            while(st.size()) {
                int now = (*st.begin()).second;
                if(shop[now]) {
                    cout << d[now] << endl;
                    break;
                }
                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(d[to] > d[now] + len || (d[to] == 0 && to != start)) {
                        st.erase({d[to], to});
                        d[to] = d[now] + len;
                        st.insert({d[to], to});
                        path.insert(to);
                    }
                }
            }
            for(set< int >::iterator it = path.begin(); it != path.end(); it++) {
                d[*it] = 0;
            }
        }
    }
}

Compilation message

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

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 5068 KB Output is correct
2 Incorrect 12 ms 5068 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 5068 KB Output is correct
2 Incorrect 12 ms 5068 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 12988 KB Output is correct
2 Correct 111 ms 12648 KB Output is correct
3 Correct 131 ms 12824 KB Output is correct
4 Correct 112 ms 14044 KB Output is correct
5 Correct 105 ms 14208 KB Output is correct
6 Correct 114 ms 15752 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 5068 KB Output is correct
2 Incorrect 12 ms 5068 KB Output isn't correct
3 Halted 0 ms 0 KB -