Submission #422361

#	Time	Username	Problem	Language	Result	Execution time	Memory
422361		tengiz05	Factories (JOI14_factories)	C++17	0 / 100	128 ms	55372 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 500000, K = 20;
std::vector<std::pair<int, i64>> e[N];
int st[N][K + 1];
int lg[N + 1];
int n, P[N];
i64 D[N];
std::vector<int> pos;
void dfs(int u, int p, i64 d = 0){
    pos.push_back(u);
    D[u] = d;
    P[u] = pos.size() - 1;
    for (auto [v, w] : e[u]) {
        if (v != p) {
            dfs(v, u, d + w);
        }
        pos.push_back(u);
    }
}
inline int range(int L, int R) {
    if (L > R) std::swap(L, R);
    int j = lg[R - L + 1];
    int minimum = std::min(st[L][j], st[R - (1 << j) + 1][j]);
    return minimum;
}
inline int lca(int u, int v) {
    return range(P[u], P[v]);
}
i64 dist(int u, int v) {
    return D[u] + D[v] - 2 * D[lca(u, v)];
}
void Init(int n, int A[], int B[], int D[]) {
    lg[1] = 0;
    for (int i = 2; i <= N; i++)
        lg[i] = lg[i / 2] + 1;
    ::n = n;
    for (int i = 0; i < n - 1; i++) {
        e[A[i]].emplace_back(B[i], D[i]);
        e[B[i]].emplace_back(A[i], D[i]);
    }
    dfs(0, 0);
    for (int i = 0; i < pos.size(); i++)
        st[i][0] = pos[i];
    for (int j = 1; j <= K; j++)
        for (int i = 0; i + (1 << j) <= N; i++)
            st[i][j] = std::min(st[i][j-1], st[i + (1 << (j - 1))][j - 1]);
}
long long Query(int S, int X[], int T, int Y[]) {
    if (S + T <= 1000) {
        i64 ans = 1e16;
        for (int i = 0; i < S; i++) {
            for (int j = 0; j < T; j++) {
                ans = std::min(ans, dist(X[i], Y[j]));
            }
        }
        return ans;
    }
    std::priority_queue<std::pair<i64, int>, std::vector<std::pair<i64, int>>, std::greater<std::pair<i64, int>>> q;
    std::vector<i64> dist(n, 1e16);
    for (int i = 0; i < S; i++) {
        q.emplace(0, X[i]);
        dist[X[i]] = 0;
    }
    while (!q.empty()) {
        auto [d, u] = q.top();
        q.pop();
        if (d > dist[u]) {
            continue;
        }
        for (auto [v, w] : e[u]) {
            if (dist[v] > d + w) {
                dist[v] = d + w;
                q.emplace(dist[v], v);
            }
        }
    }
    i64 ans =  1e16;
    for (int i = 0; i < T; i++) {
        ans = std::min(ans, dist[Y[i]]);
    }
    return ans;
}

Compilation message (stderr)

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

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