oj.uz

답안 #540756

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
540756 2022-03-21T16:51:10 Z Olympia Valley (BOI19_valley) C++17
36 / 100
 3000 ms 29624 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 = -1;
        int64_t delta = 0;
        while (x != a2) {
            if (sub[x] != -1) {
                ans = chmin(ans, sub[x] + depth[b] - depth[x]);
            }
            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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 3 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 468 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 2 ms 468 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

# 결과 실행 시간 메모리 Grader output
1 Correct 365 ms 26420 KB Output is correct
2 Correct 406 ms 26348 KB Output is correct
3 Correct 519 ms 26524 KB Output is correct
4 Execution timed out 3064 ms 29624 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 3 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 468 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 2 ms 468 KB Output is correct
13 Correct 3 ms 596 KB Output is correct
14 Correct 3 ms 596 KB Output is correct
15 Correct 365 ms 26420 KB Output is correct
16 Correct 406 ms 26348 KB Output is correct
17 Correct 519 ms 26524 KB Output is correct
18 Execution timed out 3064 ms 29624 KB Time limit exceeded
19 Halted 0 ms 0 KB -