oj.uz

Submission #1053116

# Submission time Handle Problem Language Result Execution time Memory
1053116 2024-08-11T08:52:48 Z manhlinh1501 Factories (JOI14_factories) C++17
0 / 100
 20 ms 33116 KB 
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using pii = pair<int, int>;
const int MAXN = 5e5 + 5;
const int LOGN = 20;
const i64 oo64 = 1e18;
using pli = pair<i64, int>;
int N, Q;
vector<pii> adj[MAXN];
int up[MAXN][LOGN];
int depth[MAXN];
i64 dist[MAXN];

void DFS(int u, int p = -1) {
    for(auto [v, w] : adj[u]) {
        if(v == p) continue;
        dist[v] = dist[u] + w;
        depth[v] = depth[u] + 1;
        up[v][0] = u;
        for(int i = 1; i < LOGN; i++)
            up[v][i] = up[up[v][i - 1]][i - 1];
        DFS(v, u);
    }
}

int LCA(int u, int v) {
    if(depth[u] != depth[v]) {
        if(depth[u] < depth[v]) swap(u, v);
        int k = depth[u] - depth[v];
        for(int i = 0; (1 << i) <= k; i++) {
            if(k >> i & 1)
                u = up[u][i];
        }
    }
    if(u == v) return u;
    int b = 31 - __builtin_clz(depth[u] - depth[v]);
    for(int i = b; i >= 0; i--) {
        if(up[u][i] != up[v][i]) {
            u = up[u][i];
            v = up[v][i];
        }
    }
    return up[u][0];
}

void Init(int _N, int A[], int B[], int D[]) {
    N = _N;
    for(int i = 0; i < N - 1; i++) {
        int u = A[i];
        int v = B[i];
        int w = D[i];
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    DFS(0);
}

i64 get_dist(int u, int v) {
    return dist[u] + dist[v] - 2 * dist[LCA(u, v)];
}

namespace subtask1 {
    i64 Query(int S, int X[], int T, int Y[]) {
        if(S < T) {
            swap(X, Y);
            swap(S, T);
        }
        vector<i64> dist(N, oo64);
        priority_queue<pli, vector<pli>, greater<pli>> Q;
        for(int i = 0; i < S; i++) {
            int u = X[i];
            dist[u] = 0;
            Q.emplace(dist[u], u);
        }
        while(!Q.empty()) {
            pli top = Q.top();
            Q.pop();
            int u = top.second;
            if(top.first != dist[u]) continue;
            for(pii _ : adj[u]) {
                int v = _.first;
                int w = _.second;
                if(dist[v] > dist[u] + w) {
                    dist[v] = dist[u] + w;
                    Q.emplace(dist[v], v);
                }
            }
        }
        i64 ans = oo64;
        for(int i = 0; i < T; i++) {
            int u = Y[i];
            ans = min(ans, dist[u]);
        }
        return ans;
    }
}

namespace subtask2 {
    i64 Query(int S, int X[], int T, int Y[]) {
        i64 ans = oo64;
        for(int i = 0; i < S; i++) {
            for(int j = 0; j < T; j++) {
                int u = X[i];
                int v = Y[j];
                ans = min(ans, get_dist(u, v));
            }
        }
        return ans;
    }
}

i64 Query(int S, int X[], int T, int Y[]) {
    return subtask2::Query(S, X, T, Y);
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 33116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 33116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 33116 KB Output isn't correct
2 Halted 0 ms 0 KB -