oj.uz

Submission #969511

# Submission time Handle Problem Language Result Execution time Memory
969511 2024-04-25T09:06:32 Z Turkhuu Factories (JOI14_factories) C++17
15 / 100
 8000 ms 149396 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int N;
vector<ll> len, best;
vector<int> p, sz, vis, dep;
vector<vector<int>> par;
vector<vector<array<int, 2>>> adj;
void dfs(int x, int p) {
    for (int i = 0; i < 18 && par[x][i] != -1; i++) {
        par[x][i + 1] = par[par[x][i]][i];
    }
    for (auto [y, z] : adj[x]) {
        if (y == p) continue;
        par[y][0] = x;
        dep[y] = dep[x] + 1;
        len[y] = len[x] + z;
        dfs(y, x);
    }
}
void init(int x, int p) {
    sz[x] = 1;
    for (auto [y, z] : adj[x]) {
        if (vis[y] || y == p) continue;
        init(y, x);
        sz[x] += sz[y];
    }
}
int find(int x, int p, int s) {
    for (auto [y, z] : adj[x]) {
        if (vis[y] || y == p) continue;
        if (sz[y] * 2 > s) return find(y, x, s);
    }
    return x;
}
int cd(int x) {
    init(x, -1);
    x = find(x, -1, sz[x]);
    vis[x] = 1;
    for (auto [y, z] : adj[x]) {
        if (!vis[y]) {
            p[cd(y)] = x;
        }
    }
    return x;
}
int lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = 0; i < 19; i++) {
        if ((dep[x] - dep[y]) >> i & 1) {
            x = par[x][i];
        }
    }
    if (x == y) return x;
    for (int i = 18; i >= 0; i--) {
        if (par[x][i] != par[y][i]) {
            x = par[x][i];
            y = par[y][i];
        }
    }
    return par[x][0];
}
ll dis(int x, int y) {
    return len[x] + len[y] - 2 * len[lca(x, y)];
}
void Init(int n, int A[], int B[], int D[]) {
    N = n;
    p.resize(N, -1);
    sz.resize(N);
    vis.resize(N);
    adj.resize(N);
    dep.resize(N);
    len.resize(N);
    par.resize(N, vector<int>(19, -1));
    best.resize(N, 1e18);
    for (int i = 0; i < N - 1; i++) {
        adj[A[i]].push_back({B[i], D[i]});
        adj[B[i]].push_back({A[i], D[i]});
    }
    dfs(0, -1);
    cd(0);
}
ll Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S; i++) {
        for (int j = X[i]; j != -1; j = p[j]) {
            best[j] = min(best[j], dis(j, X[i]));
        }
    }
    ll ans = 1e18;
    for (int i = 0; i < T; i++) {
        for (int j = Y[i]; j != -1; j = p[j]) {
            ans = min(ans, best[j] + dis(j, Y[i]));
        }
    }
    for (int i = 0; i < S; i++) {
        for (int j = X[i]; j != -1; j = p[j]) {
            best[j] = 1e18;
        }
    }
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16988 KB Output is correct
2 Correct 622 ms 29492 KB Output is correct
3 Correct 1409 ms 29944 KB Output is correct
4 Correct 1343 ms 29376 KB Output is correct
5 Correct 1905 ms 29780 KB Output is correct
6 Correct 257 ms 29524 KB Output is correct
7 Correct 1355 ms 29484 KB Output is correct
8 Correct 1443 ms 29736 KB Output is correct
9 Correct 1970 ms 29984 KB Output is correct
10 Correct 281 ms 29688 KB Output is correct
11 Correct 1371 ms 29492 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16988 KB Output is correct
2 Correct 3091 ms 142672 KB Output is correct
3 Execution timed out 8055 ms 149396 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16988 KB Output is correct
2 Correct 622 ms 29492 KB Output is correct
3 Correct 1409 ms 29944 KB Output is correct
4 Correct 1343 ms 29376 KB Output is correct
5 Correct 1905 ms 29780 KB Output is correct
6 Correct 257 ms 29524 KB Output is correct
7 Correct 1355 ms 29484 KB Output is correct
8 Correct 1443 ms 29736 KB Output is correct
9 Correct 1970 ms 29984 KB Output is correct
10 Correct 281 ms 29688 KB Output is correct
11 Correct 1371 ms 29492 KB Output is correct
12 Correct 4 ms 16988 KB Output is correct
13 Correct 3091 ms 142672 KB Output is correct
14 Execution timed out 8055 ms 149396 KB Time limit exceeded
15 Halted 0 ms 0 KB -