Submission #852891

#	Time	Username	Problem	Language	Result	Execution time	Memory
852891		sleepntsheep	Factories (JOI14_factories)	C++17	100 / 100	6651 ms	182868 KiB

factories

#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 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67