oj.uz

Submission #540753

# Submission time Handle Problem Language Result Execution time Memory
540753 2022-03-21T16:46:28 Z Olympia Valley (BOI19_valley) C++17
36 / 100
 3000 ms 32448 KB 
#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
#include <cmath>
#include <map>
#include <random>
#include <cassert>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <limits.h>
using namespace std;
class Tree {
private:
    int root;
    vector<vector<pair<int64_t,int64_t>>> adj; //node, weight
    vector<int64_t> parent;
    vector<int64_t> depth;
    map<pair<int64_t,int64_t>,int64_t> weight;
    vector<bool> isVillage;
    vector<int64_t> sub, pre, post;
public:
    Tree (int64_t N, int64_t root) {
        adj.resize(N);
        this->root = root;
        parent.resize(N);
        depth.resize(N);
        isVillage.assign(N, false);
        sub.resize(N);
        pre.resize(N), post.resize(N);
    }
    void add_edge (int64_t u, int64_t v, int64_t w) {
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
        weight[{u, v}] = weight[{v, u}] = w;
    }
    void update_village (int u) {
        isVillage[u] = true;
    }
    int64_t cntr = 0;
    void dfs (int64_t curNode, int64_t prevNode) {
        parent[curNode] = prevNode;
        sub[curNode] = -1;
        pre[curNode] = cntr++;
        for (pair<int64_t,int64_t> p: adj[curNode]) {
            if (p.first != prevNode) {
                dfs(p.first, curNode);
                if (sub[p.first] != -1) {
                    sub[curNode] = chmin(sub[p.first] + weight[{curNode, p.first}], sub[curNode]);
                }
            }
        }
        if (curNode == root) {
            depth[curNode] = 0;
        } else {
            depth[curNode] = depth[prevNode] + weight[{curNode, prevNode}];
        }
        if (isVillage[curNode]) {
            sub[curNode] = 0;
        }
        post[curNode] = cntr++;
    }
    bool isAncestor (int64_t a, int64_t b) {
        //is a an ancestor of b?
        return (pre[a] <= pre[b] && post[a] >= post[b]);
    }
    int64_t chmin (int64_t a, int64_t b) {
        if (a == -1) return b;
        if (b == -1) return a;
        return min(a, b);
    }
    void query (int64_t a1, int64_t a2, int64_t b) {
        if (parent[a1] != a2) {
            swap(a1, a2);
        }
        //parent[a1] = a2
        if (!isAncestor(a1, b)) {
            cout << "escaped\n";
            return;
        }
        int64_t x = b;
        int64_t ans = -1;
        int64_t delta = 0;
        while (x != a2) {
            if (sub[x] != -1) {
                ans = chmin(ans, sub[x] + delta);
            }
            delta += weight[{x, parent[x]}];
            x = parent[x];
        }
        if (ans == -1) {
            cout << "oo\n";
            return;
        }
        cout << ans << '\n';
    }
    void read () {
        dfs(root, -1);
    }
};
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, S, Q, E;
    cin >> N >> S >> Q >> E;
    E--;
    Tree myTree(N, E);
    vector<pair<int64_t,int64_t>> edges;
    for (int i = 0; i < N - 1; i++) {
        int64_t u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        edges.emplace_back(u, v);
        myTree.add_edge(u, v, w);
    }
    while (S--) {
        int64_t x; cin >> x; x--;
        myTree.update_village(x);
    }
    myTree.read();
    while (Q--) {
        int64_t u, v;
        cin >> u >> v;
        u--, v--;
        myTree.query(edges[u].first, edges[u].second, v);
    }
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 4 ms 456 KB Output is correct
4 Correct 4 ms 468 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 4 ms 456 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 3 ms 608 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 3 ms 596 KB Output is correct
14 Correct 3 ms 596 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 26480 KB Output is correct
2 Correct 413 ms 30136 KB Output is correct
3 Correct 518 ms 30408 KB Output is correct
4 Execution timed out 3097 ms 32448 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 4 ms 456 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 3 ms 608 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 3 ms 596 KB Output is correct
14 Correct 3 ms 596 KB Output is correct
15 Correct 376 ms 26480 KB Output is correct
16 Correct 413 ms 30136 KB Output is correct
17 Correct 518 ms 30408 KB Output is correct
18 Execution timed out 3097 ms 32448 KB Time limit exceeded
19 Halted 0 ms 0 KB -