oj.uz

Submission #495511

# Submission time Handle Problem Language Result Execution time Memory
495511 2021-12-19T08:06:19 Z LittleCube Valley (BOI19_valley) C++14
100 / 100
 2511 ms 128996 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

const ll INF = 1e17;

ll N, Sh, Q, E, head[20][100005], dis[20][100005], seg[20][400005], echild[20][100005], t[20], vis[100005], sz[100005], dfsorder[20][100005];
pii io[20][100005];
bool isshop[100005], hide[20][400005];
vector<pair<int, pll>> edge[100005];

void dfs_sz(int k, int layer)
{
    vis[k] = 1;
    sz[k] = 1;
    for (auto p : edge[k])
        if (!vis[p.F])
        {
            dfs_sz(p.F, layer);
            sz[k] += sz[p.F];
        }
    vis[k] = 0;
}

int dfs_find_cent(int k, int layer, int root)
{
    vis[k] = 1;
    bool valid = true;
    for (auto p : edge[k])
        if (!vis[p.F])
        {
            int cent = dfs_find_cent(p.F, layer, root);
            if (cent)
            {
                vis[k] = 0;
                return cent;
            }
            if (sz[p.F] > sz[root] / 2)
                valid = false;
        }
    vis[k] = 0;
    if (valid && sz[root] - sz[k] <= sz[root] / 2)
        return k;
    return 0;
}

void dfs_init(int k, int layer, int root)
{
    vis[k] = 1;

    io[layer][k].F = ++t[layer];
    dfsorder[layer][io[layer][k].F] = k;
    head[layer][k] = root;
    for (auto p : edge[k])
        if (!vis[p.F])
        {
            dis[layer][p.F] = dis[layer][k] + p.S.S;
            echild[layer][p.S.F] = p.F;
            dfs_init(p.F, layer, root);
        }
    vis[k] = 0;
    io[layer][k].S = t[layer];
}

void cent_dec(int root, int layer)
{
    assert(layer <= 18);
    dfs_sz(root, layer);
    int cent = dfs_find_cent(root, layer, root);
    dfs_init(cent, layer, cent);
    vis[cent] = 1;
    for (auto p : edge[cent])
        if (!vis[p.F])
            cent_dec(p.F, layer + 1);
}

void build(int layer, int i = 1, int L = 1, int R = N)
{
    if (L == R)
    {
        int u = dfsorder[layer][L];
        if (isshop[u])
            seg[layer][i] = dis[layer][u];
        else
            seg[layer][i] = INF;
    }
    else
    {
        int mid = (L + R) / 2;
        build(layer, i * 2, L, mid);
        build(layer, i * 2 + 1, mid + 1, R);
        seg[layer][i] = min(seg[layer][i * 2], seg[layer][i * 2 + 1]);
    }
}

ll getval(int layer, int i)
{
    if (hide[layer][i])
        return INF;
    else
        return seg[layer][i];
}

void modify(int layer, int mL, int mR, bool val, int i = 1, int L = 1, int R = N)
{
    if (mL <= L && R <= mR)
        hide[layer][i] = val;
    else if (mR < L || R < mL)
        return;
    else
    {
        int mid = (L + R) / 2;
        modify(layer, mL, mR, val, i * 2,         L, mid);
        modify(layer, mL, mR, val, i * 2 + 1, mid + 1, R);
        seg[layer][i] = min(getval(layer, i * 2), getval(layer, i * 2 + 1));
    }
}

ll query(int layer, int qL, int qR, int i = 1, int L = 1, int R = N)
{
    if (qL <= L && R <= qR)
        return getval(layer, i);
    else if (qR < L || R < qL)
        return INF;
    else
    {
        int mid = (L + R) / 2;
        return min(query(layer, qL, qR, i * 2, L, mid),
                   query(layer, qL, qR, i * 2 + 1, mid + 1, R));
    }
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> Sh >> Q >> E;
    assert(Q <= 100000);
    for (int i = 1; i < N; i++)
    {
        int A, B, W;
        cin >> A >> B >> W;
        edge[A].emplace_back(make_pair(B, pll{i, W}));
        edge[B].emplace_back(make_pair(A, pll{i, W}));
    }
    for (int i = 1; i <= Sh; i++)
    {
        int u;
        cin >> u;
        isshop[u] = 1;
    }
    cent_dec(1, 0);
    for (int i = 0; i < 20; i++)
        dis[i][E] = -INF;
    isshop[E] = 1;
    for (int i = 0; i < 20; i++)
        build(i);
    for (int i = 1; i <= Q; i++)
    {
        ll ans = INF, I, R;
        cin >> I >> R;
        for (int l = 0; l < 20; l++)
            if (head[l][R])
            {
                int snow = echild[l][I];

                if (!(io[l][snow].F <= io[l][R].F && io[l][R].S <= io[l][snow].S))
                {
                    modify(l, io[l][snow].F, io[l][snow].S, 1);
                    ans = min(ans, dis[l][R] + query(l, io[l][head[l][R]].F, io[l][head[l][R]].S));
                    modify(l, io[l][snow].F, io[l][snow].S, 0);

                    //cout << ans << " ";
                }
            }
        if (ans < 0)
            cout << "escaped\n";
        else if (ans >= 1e15)
            cout << "oo\n";
        else
            cout << ans << '\n';
    }
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3324 KB Output is correct
2 Correct 16 ms 3356 KB Output is correct
3 Correct 19 ms 3328 KB Output is correct
4 Correct 21 ms 3280 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3324 KB Output is correct
2 Correct 16 ms 3356 KB Output is correct
3 Correct 19 ms 3328 KB Output is correct
4 Correct 21 ms 3280 KB Output is correct
5 Correct 4 ms 3708 KB Output is correct
6 Correct 4 ms 3920 KB Output is correct
7 Correct 8 ms 4176 KB Output is correct
8 Correct 4 ms 3664 KB Output is correct
9 Correct 5 ms 3952 KB Output is correct
10 Correct 6 ms 4048 KB Output is correct
11 Correct 4 ms 3664 KB Output is correct
12 Correct 5 ms 3968 KB Output is correct
13 Correct 6 ms 4048 KB Output is correct
14 Correct 6 ms 4048 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 84852 KB Output is correct
2 Correct 950 ms 106940 KB Output is correct
3 Correct 1274 ms 115940 KB Output is correct
4 Correct 1720 ms 125528 KB Output is correct
5 Correct 2157 ms 123580 KB Output is correct
6 Correct 2439 ms 128996 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3324 KB Output is correct
2 Correct 16 ms 3356 KB Output is correct
3 Correct 19 ms 3328 KB Output is correct
4 Correct 21 ms 3280 KB Output is correct
5 Correct 4 ms 3708 KB Output is correct
6 Correct 4 ms 3920 KB Output is correct
7 Correct 8 ms 4176 KB Output is correct
8 Correct 4 ms 3664 KB Output is correct
9 Correct 5 ms 3952 KB Output is correct
10 Correct 6 ms 4048 KB Output is correct
11 Correct 4 ms 3664 KB Output is correct
12 Correct 5 ms 3968 KB Output is correct
13 Correct 6 ms 4048 KB Output is correct
14 Correct 6 ms 4048 KB Output is correct
15 Correct 524 ms 84852 KB Output is correct
16 Correct 950 ms 106940 KB Output is correct
17 Correct 1274 ms 115940 KB Output is correct
18 Correct 1720 ms 125528 KB Output is correct
19 Correct 2157 ms 123580 KB Output is correct
20 Correct 2439 ms 128996 KB Output is correct
21 Correct 443 ms 82888 KB Output is correct
22 Correct 901 ms 106612 KB Output is correct
23 Correct 1211 ms 114836 KB Output is correct
24 Correct 1818 ms 124584 KB Output is correct
25 Correct 2511 ms 127336 KB Output is correct
26 Correct 485 ms 84080 KB Output is correct
27 Correct 928 ms 106664 KB Output is correct
28 Correct 1279 ms 115832 KB Output is correct
29 Correct 1842 ms 124932 KB Output is correct
30 Correct 2400 ms 125136 KB Output is correct
31 Correct 435 ms 82476 KB Output is correct
32 Correct 873 ms 107872 KB Output is correct
33 Correct 1306 ms 115052 KB Output is correct
34 Correct 1779 ms 124848 KB Output is correct
35 Correct 2447 ms 126424 KB Output is correct
36 Correct 1689 ms 123376 KB Output is correct