oj.uz

Submission #852886

# Submission time Handle Problem Language Result Execution time Memory
852886 2023-09-23T04:30:03 Z sleepntsheep Factories (JOI14_factories) C++17
0 / 100
 1940 ms 143604 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 root_dis[N], tin[N], tout[N], depth[N], timer = 1, P[20][N];


void dfs(int u, int p, int 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<int, 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, int 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<int, 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) vt[u].clear();
    return z;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 88880 KB Output is correct
2 Incorrect 1940 ms 102268 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 88664 KB Output is correct
2 Incorrect 1733 ms 143604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 88880 KB Output is correct
2 Incorrect 1940 ms 102268 KB Output isn't correct
3 Halted 0 ms 0 KB -