oj.uz

Submission #852891

# Submission time Handle Problem Language Result Execution time Memory
852891 2023-09-23T04:33:16 Z sleepntsheep Factories (JOI14_factories) C++17
100 / 100
 6651 ms 182868 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <set>
#include <utility>
#include <map>
#include <array>

#include "factories.h"
using namespace std;
#define ALL(x) x.begin(), x.end()

const int N = 500005;
vector<pair<int, int>> g[N];

int tin[N], tout[N], depth[N], timer = 1, P[20][N];
long long root_dis[N];


void dfs(int u, int p, long long ds, int lv)
{
    depth[u] = lv;
    P[0][u] = p;
    for (int j = 1; j < 20; ++j) P[j][u] = P[j-1][P[j-1][u]];
    root_dis[u] = ds;
    tin[u] = timer++;
    for (auto [w, v] : g[u])
        if (v != p) dfs(v, u, ds + w, lv+1);
    tout[u] = timer;
}

bool in_subtree(int lo, int hi)
{
    return tin[hi] <= tin[lo] && tout[lo] <= tout[hi];
}

int lca(int u, int v)
{
    if (depth[u] < depth[v]) swap(u, v);
    int dt = depth[u] - depth[v];
    for (int j = 20; j--;) if (dt & (1 << j)) u = P[j][u];
    if (u == v) return u;
    for (int j = 20; j--;) if (P[j][u] != P[j][v]) u = P[j][u], v = P[j][v];
    return P[0][u];
}

void Init(int n, int *a, int *b, int *d)
{
    for (int i = 0; i + 1 < n; ++i) g[a[i]].emplace_back(d[i], b[i]), g[b[i]].emplace_back(d[i], a[i]);
    dfs(1, 1, 0, 1);
}

vector<int> V;
vector<pair<long long, int>> vt[N];

long long Query(int s, int *x, int t, int *y)
{
    V.clear();
    for (int i = 0; i < s; ++i) V.push_back(i[x]);
    for (int i = 0; i < t; ++i) V.push_back(i[y]);

    sort(ALL(V), [&](int a, int b) { return tin[a] < tin[b]; });

    for (int i = 1; i < s+t; ++i) V.push_back(lca(V[i-1], V[i]));
    
    sort(ALL(V), [&](int a, int b) { return tin[a] < tin[b]; });

    V.erase(unique(ALL(V)), V.end());

    auto add_edge_vt = [&](int u, int v, long long w) {
        vt[u].emplace_back(w, v);
        vt[v].emplace_back(w, u);
    };

    {
        vector<int> st;
        for (auto u : V)
        {
            while (st.size() && !in_subtree(u, st.back())) st.pop_back();
            if (st.size()) add_edge_vt(st.back(), u, root_dis[u] - root_dis[st.back()]);
            st.push_back(u);
        }
    }

    map<int, long long> dp;
    priority_queue<pair<long long, int>> pq;
    for (int i = 0; i < s; ++i) pq.emplace(dp[i[x]] = 0, i[x]);
    while (pq.size())
    {
        auto [c, u] = pq.top(); pq.pop(); c=-c;
        if (dp[u] != c) continue;
        for (auto [w, v] : vt[u])
            if (!dp.count(v) || w + c < dp[v]) pq.emplace(-(dp[v] = w + c), v);
    }

    long long z = 1e18;
    for (int i = 0; i < t; ++i) z = min(z, dp[i[y]]);

    for (auto u : V) vector<pair<long long, int>>().swap(vt[u]);
    return z;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 88664 KB Output is correct
2 Correct 2105 ms 94012 KB Output is correct
3 Correct 2189 ms 93212 KB Output is correct
4 Correct 1986 ms 103128 KB Output is correct
5 Correct 1704 ms 102920 KB Output is correct
6 Correct 1297 ms 103040 KB Output is correct
7 Correct 2167 ms 102436 KB Output is correct
8 Correct 2147 ms 103280 KB Output is correct
9 Correct 1690 ms 103024 KB Output is correct
10 Correct 1313 ms 102948 KB Output is correct
11 Correct 2165 ms 102672 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 88664 KB Output is correct
2 Correct 1790 ms 114708 KB Output is correct
3 Correct 2234 ms 134780 KB Output is correct
4 Correct 1152 ms 133148 KB Output is correct
5 Correct 1790 ms 164004 KB Output is correct
6 Correct 2380 ms 136088 KB Output is correct
7 Correct 2084 ms 113164 KB Output is correct
8 Correct 1073 ms 113348 KB Output is correct
9 Correct 1465 ms 118100 KB Output is correct
10 Correct 1987 ms 113708 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 88664 KB Output is correct
2 Correct 2105 ms 94012 KB Output is correct
3 Correct 2189 ms 93212 KB Output is correct
4 Correct 1986 ms 103128 KB Output is correct
5 Correct 1704 ms 102920 KB Output is correct
6 Correct 1297 ms 103040 KB Output is correct
7 Correct 2167 ms 102436 KB Output is correct
8 Correct 2147 ms 103280 KB Output is correct
9 Correct 1690 ms 103024 KB Output is correct
10 Correct 1313 ms 102948 KB Output is correct
11 Correct 2165 ms 102672 KB Output is correct
12 Correct 16 ms 88664 KB Output is correct
13 Correct 1790 ms 114708 KB Output is correct
14 Correct 2234 ms 134780 KB Output is correct
15 Correct 1152 ms 133148 KB Output is correct
16 Correct 1790 ms 164004 KB Output is correct
17 Correct 2380 ms 136088 KB Output is correct
18 Correct 2084 ms 113164 KB Output is correct
19 Correct 1073 ms 113348 KB Output is correct
20 Correct 1465 ms 118100 KB Output is correct
21 Correct 1987 ms 113708 KB Output is correct
22 Correct 6185 ms 151876 KB Output is correct
23 Correct 4654 ms 154572 KB Output is correct
24 Correct 6651 ms 156820 KB Output is correct
25 Correct 6037 ms 156040 KB Output is correct
26 Correct 5881 ms 141136 KB Output is correct
27 Correct 3852 ms 182868 KB Output is correct
28 Correct 3213 ms 150636 KB Output is correct
29 Correct 5277 ms 139520 KB Output is correct
30 Correct 5084 ms 140504 KB Output is correct
31 Correct 5078 ms 140968 KB Output is correct
32 Correct 2543 ms 129284 KB Output is correct
33 Correct 2138 ms 124988 KB Output is correct
34 Correct 3608 ms 112208 KB Output is correct
35 Correct 3213 ms 112256 KB Output is correct
36 Correct 3610 ms 112904 KB Output is correct
37 Correct 3353 ms 113080 KB Output is correct