oj.uz

Submission #391644

# Submission time Handle Problem Language Result Execution time Memory
391644 2021-04-19T13:02:27 Z abdzag Valley (BOI19_valley) C++17
59 / 100
 3000 ms 26216 KB 
#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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 332 KB Output is correct
2 Correct 32 ms 360 KB Output is correct
3 Correct 32 ms 368 KB Output is correct
4 Correct 18 ms 332 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 332 KB Output is correct
2 Correct 32 ms 360 KB Output is correct
3 Correct 32 ms 368 KB Output is correct
4 Correct 18 ms 332 KB Output is correct
5 Correct 11 ms 460 KB Output is correct
6 Correct 16 ms 540 KB Output is correct
7 Correct 21 ms 536 KB Output is correct
8 Correct 11 ms 460 KB Output is correct
9 Correct 15 ms 528 KB Output is correct
10 Correct 22 ms 536 KB Output is correct
11 Correct 3 ms 464 KB Output is correct
12 Correct 3 ms 460 KB Output is correct
13 Correct 3 ms 456 KB Output is correct
14 Correct 23 ms 528 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 19648 KB Output is correct
2 Correct 313 ms 23476 KB Output is correct
3 Correct 321 ms 23472 KB Output is correct
4 Correct 340 ms 24640 KB Output is correct
5 Correct 313 ms 24744 KB Output is correct
6 Correct 328 ms 26216 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 332 KB Output is correct
2 Correct 32 ms 360 KB Output is correct
3 Correct 32 ms 368 KB Output is correct
4 Correct 18 ms 332 KB Output is correct
5 Correct 11 ms 460 KB Output is correct
6 Correct 16 ms 540 KB Output is correct
7 Correct 21 ms 536 KB Output is correct
8 Correct 11 ms 460 KB Output is correct
9 Correct 15 ms 528 KB Output is correct
10 Correct 22 ms 536 KB Output is correct
11 Correct 3 ms 464 KB Output is correct
12 Correct 3 ms 460 KB Output is correct
13 Correct 3 ms 456 KB Output is correct
14 Correct 23 ms 528 KB Output is correct
15 Correct 296 ms 19648 KB Output is correct
16 Correct 313 ms 23476 KB Output is correct
17 Correct 321 ms 23472 KB Output is correct
18 Correct 340 ms 24640 KB Output is correct
19 Correct 313 ms 24744 KB Output is correct
20 Correct 328 ms 26216 KB Output is correct
21 Execution timed out 3057 ms 20884 KB Time limit exceeded
22 Halted 0 ms 0 KB -