Submission #391644

#	Time	Username	Problem	Language	Result	Execution time	Memory
391644		abdzag	Valley (BOI19_valley)	C++17	59 / 100	3057 ms	26216 KiB

valley

#include<bits/stdc++.h>
#include<unordered_set>

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define PI 3.141592653
#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define rrep(i,a,b) for(int i = a; i>int(b);--i)
#define all(v) v.begin(),v.end()
#define trav(a, x) for(auto& a : x)

typedef long long ll;


const long long inf = 1e15;

using namespace std;

void printint(vector < ll > vec)
{
    for (auto a : vec) {
        cout << a << " ";
    }
    cout << endl;
}
void printstr(vector < string > vec)
{
    for (auto a : vec) {
        cout << a << endl;
    }
}
void printchar(vector < char > vec)
{
    for (auto a : vec) {
        cout << a;
    }
    cout << endl;
}
void print2d(vector < vector < ll >> vec)
{
    for (int i = 0; i < vec.size(); i++) {
        printint(vec[i]);
    }
    cout << endl;
}
void printmap(map<int, long double> myMap) {
    for (auto it = myMap.cbegin(); it != myMap.cend(); ++it)
    {
        std::cout << it->first << " ";
        cout << it->second << " ";
    }
}
void print2dchar(vector < vector < char >> vec)
{
    for (auto a : vec) {
        printchar(a);
    }
    cout << endl;
}
bool sortcol(const vector<int>& v1,
    const vector<int>& v2) {
    return v1[1] < v2[1];
}
void printsetint(set<ll> s) {
    for (auto it = s.begin(); it != s.end(); ++it) {
        cout << *it;
    }
}
void printsetpairint(set<pair<int, int>> s) {
    for (auto it = s.begin(); it != s.end(); ++it) {
        pair<int, int> cur = *it;
        cout << cur.first << " " << cur.second;
    }
    cout << endl;
}
void printsetstring(set<string> s) {
    for (auto it = s.begin(); it != s.end(); ++it) {
        cout << *it << endl;
    }
}
struct MaxTree {
    typedef int T;
    static constexpr T unit = INT_MIN;
    T f(T a, T b) { return max(a, b); } // (any associative fn)
    vector<T> s; int n;
    MaxTree(int n = 0, T def = unit) : s(2 * n, def), n(n) {}
    void update(int pos, T val) {
        for (s[pos += n] = val; pos /= 2;)
            s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
    }
    T query(int b, int e) { // query [b, e)
        T ra = unit, rb = unit;
        for (b += n, e += n; b < e; b /= 2, e /= 2) {
            if (b % 2) ra = f(ra, s[b++]);
            if (e % 2) rb = f(s[--e], rb);
        }
        return f(ra, rb);
    }
};
struct MinTree {
    typedef int T;
    static constexpr T unit = INT_MAX;
    T f(T a, T b) { return min(a, b); } // (any associative fn)
    vector<T> s; int n;
    MinTree(int n = 0, T def = unit) : s(2 * n, def), n(n) {}
    void update(int pos, T val) {
        for (s[pos += n] = val; pos /= 2;)
            s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
    }
    T query(int b, int e) { // query [b, e)
        T ra = unit, rb = unit;
        for (b += n, e += n; b < e; b /= 2, e /= 2) {
            if (b % 2) ra = f(ra, s[b++]);
            if (e % 2) rb = f(s[--e], rb);
        }
        return f(ra, rb);
    }
};
vector<vector<pair<ll,ll>>> tree;
vector<vector<pair<ll,ll>>> g;
vector<ll> occurences;
vector<pair<ll, ll>> when;
void dfs(ll cur) {
    when[cur].first = occurences.size();
    occurences.push_back(cur);
    trav(v, tree[cur]) dfs(v.first);
    when[cur].second = occurences.size();
    occurences.push_back(cur);
}
int main()
{
    cin.sync_with_stdio(false);
    ll n,s,Q,e;
    cin >> n>>s>>Q>>e;
    g.resize(n + 1);
    tree.resize(n + 1);
    when.resize(n + 1);
    vector<pair<ll,ll>>edges(n);
    vector<ll> parents(n + 1);
    rep(i, 1, n) {
        ll a, b,w;
        cin >> a >> b>>w;
        edges[i] = make_pair(a, b);
        g[a].emplace_back(b,w);
        g[b].emplace_back(a,w);
    }
    vector<ll> is_shop(n + 1);
    rep(i, 0, s) {
        ll a;
        cin >> a;
        is_shop[a] = true;
    }
    vector<bool> visitedChild(n + 1);
    queue<ll> q;
    q.push(e);
    while (!q.empty()) {
        ll cur = q.front();
        q.pop();
        visitedChild[cur] = true;
        rep(i, 0, g[cur].size()) {
            ll v = g[cur][i].first;
            ll w = g[cur][i].second;
            if (!visitedChild[v]) {
                tree[cur].emplace_back(v,w);
                parents[v] = cur;
                q.push(v);
            }
        }
    }
    if (s == n) {
        dfs(e);
        rep(i, 0, Q) {
            ll a, b;
            cin >> a >> b;
            ll parent;
            if (parents[edges[a].first] == edges[a].second) {
                parent = edges[a].first;
            }
            else if (parents[edges[a].second] == edges[a].first) {
                parent = edges[a].second;
            }
            else cout << "cringe" << endl;
            if (when[b].first >= when[parent].first && when[b].first <= when[parent].second) {
                cout << 0 << endl;
            }
            else cout << "escaped" << endl;
        }
    }
    else {
        rep(i, 0, Q) {
            ll a, b;
            cin >> a >> b;
            queue<ll> bfs;
            ll dist = inf;
            if (is_shop[b])dist = 0;
            vector<ll> dists(n + 1,-1);
            dists[b] = 0;
            bfs.push(b);
            while(!bfs.empty()) {
                ll cur = bfs.front();
                bfs.pop();
                trav(v, g[cur]) {
                    if (dists[v.first]==-1) {
                        if (make_pair(v.first, cur) != edges[a] && make_pair(cur, v.first) != edges[a]) {
                            bfs.push(v.first);
                            dists[v.first] = dists[cur] + v.second;
                            if (is_shop[v.first])dist = min(dist, dists[v.first]);
                        }
                    }
                }
            }
            if (dists[e] != -1) {
                cout << "escaped" << endl;
            }
            else {
                if (dist == inf) {
                    cout << "oo" << endl;
                }
                else cout << dist << endl;
            }
        }
    }
    return 0;
}

Compilation message (stderr)

valley.cpp: In function 'void print2d(std::vector<std::vector<long long int> >)':
valley.cpp:40:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for (int i = 0; i < vec.size(); i++) {
      |                     ~~^~~~~~~~~~~~
valley.cpp: In function 'int main()':
valley.cpp:182:45: warning: 'parent' may be used uninitialized in this function [-Wmaybe-uninitialized]
  182 |             if (when[b].first >= when[parent].first && when[b].first <= when[parent].second) {
      |                                             ^

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