oj.uz

Submission #200560

# Submission time Handle Problem Language Result Execution time Memory
200560 2020-02-07T09:27:47 Z johutha Valley (BOI19_valley) C++17
59 / 100
 3000 ms 29928 KB 
#include <vector>
#include <iostream>

#define int int64_t

using namespace std;

int log2(int n)
{
    int res = 0;
    for (; n; n >>= 1) res++;
    return res;
}

struct graph
{
    vector<vector<pair<int,int>>> adjlist;
    vector<vector<int>> lcatable;
    vector<int> lvl;
    int n;
    int logn;
    int rt;
    vector<bool> shop;

    void builddfs(int curr, int par, int l)
    {
        lvl[curr] = l;
        lcatable[0][curr] = par;

        for (auto p : adjlist[curr])
        {
            auto next = p.first;
            if (next == par) continue;
            builddfs(next, curr, l + 1);
        }
    }

    void build()
    {
        logn = log2(n);
        lcatable.resize(logn, vector<int>(n));
        lvl.resize(n, - 1);

        builddfs(rt, -1, 0);

        for (int l = 1; l < logn; l++)
        {
            for (int i = 0; i < n; i++)
            {
                lcatable[l][i] = (lcatable[l - 1][i] == -1) ? -1 : lcatable[l - 1][lcatable[l - 1][i]];
            }
        }
    }

    int lca(int a, int b)
    {
        if (lvl[a] < lvl[b]) swap(a, b);
        int ldiff = lvl[a] - lvl[b];

        int e = 1;
        for (int i = 0; i < logn; i++)
        {
            if (ldiff & e) a = lcatable[i][a];
            e *= 2;
        }

        if (a == b) return a;

        for (int i = 0; i < logn; i++)
        {
            if (lcatable[i][a] != lcatable[i][b])
            {
                a = lcatable[i][a];
                b = lcatable[i][b];
            }
        }

        return lcatable[0][a];
    }

    int ddfs(int curr, int par, pair<int,int> fb)
    {
        // cerr << curr << " " << shop[curr] << "\n";
        if (shop[curr] == true) return 0;
        int mmin = 1e15;

        for (auto p : adjlist[curr])
        {
            int next = p.first;
            if (next == par) continue;
            if (min(fb.first, fb.second) == min(curr, next) && max(fb.first, fb.second) == max(curr, next)) continue;
            mmin = min(mmin, p.second + ddfs(next, curr, fb));
        }
        return mmin;
    }
};

signed main()
{
    int n, s, q, r;
    cin >> n >> s >> q >> r;

    graph g;
    g.rt = r - 1;
    g.n = n;
    g.adjlist.resize(n);
    g.shop.resize(n, false);
    
    vector<pair<int,int>> edges;

    for (int i = 0; i < n - 1; i++)
    {
        int a, b, w;
        cin >> a >> b >> w;
        a--; b--;
        edges.emplace_back(a, b);
        g.adjlist[a].emplace_back(b, w);
        g.adjlist[b].emplace_back(a, w);
    }

    for (int i = 0; i < s; i++)
    {
        int p;
        cin >> p;
        p--;
        g.shop[p] = true;
    }

    g.build();

    for (int i = 0; i < q; i++)
    {
        int r, v;
        cin >> r >> v;
        r--;
        v--;
        auto p = edges[r];
        if (g.lvl[p.first] > g.lvl[p.second]) swap(p.first, p.second);

        if (g.lca(p.second, v) != p.second)
        {
            cout << "escaped\n";
            continue;
        }

        int d = g.ddfs(v, -1, p);
        if (d >= 1e15)
        {
            cout << "oo\n";
        }
        else
        {
            cout << d << "\n";
        }
    }
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 376 KB Output is correct
2 Correct 32 ms 504 KB Output is correct
3 Correct 32 ms 632 KB Output is correct
4 Correct 32 ms 504 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 376 KB Output is correct
2 Correct 32 ms 504 KB Output is correct
3 Correct 32 ms 632 KB Output is correct
4 Correct 32 ms 504 KB Output is correct
5 Correct 9 ms 504 KB Output is correct
6 Correct 9 ms 508 KB Output is correct
7 Correct 10 ms 632 KB Output is correct
8 Correct 9 ms 504 KB Output is correct
9 Correct 9 ms 504 KB Output is correct
10 Correct 10 ms 632 KB Output is correct
11 Correct 10 ms 504 KB Output is correct
12 Correct 9 ms 504 KB Output is correct
13 Correct 10 ms 504 KB Output is correct
14 Correct 13 ms 504 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 586 ms 24168 KB Output is correct
2 Correct 599 ms 27904 KB Output is correct
3 Correct 645 ms 28008 KB Output is correct
4 Correct 685 ms 28776 KB Output is correct
5 Correct 724 ms 29212 KB Output is correct
6 Correct 754 ms 29928 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 376 KB Output is correct
2 Correct 32 ms 504 KB Output is correct
3 Correct 32 ms 632 KB Output is correct
4 Correct 32 ms 504 KB Output is correct
5 Correct 9 ms 504 KB Output is correct
6 Correct 9 ms 508 KB Output is correct
7 Correct 10 ms 632 KB Output is correct
8 Correct 9 ms 504 KB Output is correct
9 Correct 9 ms 504 KB Output is correct
10 Correct 10 ms 632 KB Output is correct
11 Correct 10 ms 504 KB Output is correct
12 Correct 9 ms 504 KB Output is correct
13 Correct 10 ms 504 KB Output is correct
14 Correct 13 ms 504 KB Output is correct
15 Correct 586 ms 24168 KB Output is correct
16 Correct 599 ms 27904 KB Output is correct
17 Correct 645 ms 28008 KB Output is correct
18 Correct 685 ms 28776 KB Output is correct
19 Correct 724 ms 29212 KB Output is correct
20 Correct 754 ms 29928 KB Output is correct
21 Correct 610 ms 27740 KB Output is correct
22 Correct 705 ms 27456 KB Output is correct
23 Correct 2093 ms 27624 KB Output is correct
24 Execution timed out 3021 ms 27500 KB Time limit exceeded
25 Halted 0 ms 0 KB -