oj.uz

Submission #1053105

# Submission time Handle Problem Language Result Execution time Memory
1053105 2024-08-11T08:48:22 Z manhlinh1501 Factories (JOI14_factories) C++17
15 / 100
 8000 ms 103984 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[i];
                ans = min(ans, get_dist(u, v));
            }
        }
        return ans;
    }
}

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 33116 KB Output is correct
2 Correct 1929 ms 37616 KB Output is correct
3 Correct 1822 ms 37696 KB Output is correct
4 Correct 1856 ms 37864 KB Output is correct
5 Correct 978 ms 37856 KB Output is correct
6 Correct 2071 ms 38008 KB Output is correct
7 Correct 1834 ms 37700 KB Output is correct
8 Correct 1748 ms 37872 KB Output is correct
9 Correct 1008 ms 37972 KB Output is correct
10 Correct 2178 ms 37868 KB Output is correct
11 Correct 1755 ms 37708 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 33308 KB Output is correct
2 Execution timed out 8071 ms 103984 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 33116 KB Output is correct
2 Correct 1929 ms 37616 KB Output is correct
3 Correct 1822 ms 37696 KB Output is correct
4 Correct 1856 ms 37864 KB Output is correct
5 Correct 978 ms 37856 KB Output is correct
6 Correct 2071 ms 38008 KB Output is correct
7 Correct 1834 ms 37700 KB Output is correct
8 Correct 1748 ms 37872 KB Output is correct
9 Correct 1008 ms 37972 KB Output is correct
10 Correct 2178 ms 37868 KB Output is correct
11 Correct 1755 ms 37708 KB Output is correct
12 Correct 16 ms 33308 KB Output is correct
13 Execution timed out 8071 ms 103984 KB Time limit exceeded
14 Halted 0 ms 0 KB -