Submission #571322

#	Time	Username	Problem	Language	Result	Execution time	Memory
571322		timreizin	Factories (JOI14_factories)	C++17	0 / 100	26 ms	664 KiB

factories

#include "factories.h"
#include <vector>
#include <array>
#include <algorithm>
#include <stack>
#include <queue>

using ll = long long;
using namespace std;

vector<int> tin, tout;
vector<vector<pair<int, ll>>> adj;
vector<ll> d, h;
vector<bool> used;
vector<array<int, 20>> up;

void Init(int n, int A[], int B[], int D[])
{
    tin.resize(n);
    tout.resize(n);
    h.resize(n);
    up.resize(n);
    d.resize(n, 1e18);
    used.resize(n);
    ::adj.resize(n);
    vector<vector<pair<int, ll>>> adj(n);
    for (int i = 0; i + 1 < n; ++i)
    {
        adj[A[i]].emplace_back(B[i], D[i]);
        adj[B[i]].emplace_back(A[i], D[i]);
    }
    int t = 0;
    auto dfs = [&t, &adj](auto self, int v, int p) -> void
    {
        up[v][0] = p;
        for (int i = 1; i < 20; ++i) up[v][i] = up[up[v][i - 1]][i - 1];
        tin[v] = t++;
        for (auto [u, w] : adj[v])
        {
            if (u != p)
            {
                h[u] = h[v] + w;
                self(self, u, v);
            }
        }
        tout[v] = t - 1;
    };
    dfs(dfs, 0, 0);
}

bool isParent(int p, int c)
{
    return tin[p] <= tin[c] && tout[p] >= tout[c];
}

int lca(int a, int b)
{
    if (isParent(a, b)) return a;
    if (isParent(b, a)) return b;
    for (int i = 19; i >= 0; --i) if (!isParent(up[a][i], b)) a = up[a][i];
    return up[a][0];
}

ll dist(int a, int b)
{
    return h[a] + h[b] - 2 * h[lca(a, b)];
}

ll Query(int s, int x[], int t, int y[])
{
    vector<int> vertices;
    for (int i = 0; i < s; ++i) vertices.push_back(x[i]);
    for (int i = 0; i < t; ++i) vertices.push_back(y[i]);
    sort(vertices.begin(), vertices.end(), [](int a, int b){ return tin[a] < tin[b]; });
    int sz = vertices.size();
    for (int i = 0; i + 1 < sz; ++i) vertices.push_back(lca(vertices[i], vertices[i + 1]));
    sort(vertices.begin(), vertices.end(), [](int a, int b){ return tin[a] < tin[b]; });
    vertices.erase(unique(vertices.begin(), vertices.end()), vertices.end());
    stack<int> help;
    help.push(vertices.front());
    for (int i = 1; i < vertices.size(); ++i)
    {
        while (!isParent(help.top(), vertices[i])) help.pop();
        adj[help.top()].emplace_back(vertices[i], dist(help.top(), vertices[i]));
        adj[vertices[i]].emplace_back(help.top(), dist(help.top(), vertices[i]));
        help.push(vertices[i]);
    }
    priority_queue<pair<ll, int>> pq;
    for (int i = 0; i < s; ++i)
    {
        pq.push({0, x[i]});
        d[x[i]] = 0;
    }
    while (!pq.empty())
    {
        auto [ndn, v] = pq.top();
        pq.pop();
        if (used[v]) continue;
        used[v] = true;
        for (auto [u, w] : adj[v])
        {
            if (d[u] > d[v] + w)
            {
                d[u] = d[v] + w;
                pq.push({d[u], u});
            }
        }
    }
    ll res = 1e18;
    for (int i = 0; i < t; ++i) res = min(res, d[y[i]]);
    for (int i : vertices)
    {
        used[i] = false;
        adj[i].clear();
        d[i] = 1e18;
    }
    return res;
}

Compilation message (stderr)

factories.cpp: In function 'll Query(int, int*, int, int*)':
factories.cpp:81:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for (int i = 1; i < vertices.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67