oj.uz

Submission #540759

# Submission time Handle Problem Language Result Execution time Memory
540759 2022-03-21T16:53:07 Z Olympia Valley (BOI19_valley) C++17
36 / 100
 3000 ms 29632 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++;
        if (curNode == root) {
            depth[curNode] = 0;
        } else {
            depth[curNode] = depth[prevNode] + weight[{curNode, prevNode}];
        }
        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 (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);
        }
        if (!isAncestor(a1, b)) {
            cout << "escaped\n";
            return;
        }
        int64_t x = b;
        int64_t ans = LLONG_MAX;
        int64_t delta = 0;
        while (x != a2) {
            if (sub[x] != -1) {
                ans = min(ans, sub[x] + depth[b] - depth[x]);
            }
            delta += weight[{x, parent[x]}];
            x = parent[x];
        }
        if (ans == LLONG_MAX) {
            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 364 KB Output is correct
2 Correct 3 ms 436 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 4 ms 340 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 364 KB Output is correct
2 Correct 3 ms 436 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 584 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 2 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 403 ms 26428 KB Output is correct
2 Correct 402 ms 26280 KB Output is correct
3 Correct 509 ms 26504 KB Output is correct
4 Execution timed out 3088 ms 29632 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 364 KB Output is correct
2 Correct 3 ms 436 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 584 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 3 ms 596 KB Output is correct
15 Correct 403 ms 26428 KB Output is correct
16 Correct 402 ms 26280 KB Output is correct
17 Correct 509 ms 26504 KB Output is correct
18 Execution timed out 3088 ms 29632 KB Time limit exceeded
19 Halted 0 ms 0 KB -