oj.uz

Submission #1046534

# Submission time Handle Problem Language Result Execution time Memory
1046534 2024-08-06T16:17:45 Z Turkhuu Factories (JOI14_factories) C++17
100 / 100
 2281 ms 196760 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int N;
vector<vector<pair<int, int>>> adj;
vector<vector<int>> s;
vector<int> dep, euler, pos, lg, sz, par, vis;
vector<ll> d2r, best;
void dfs(int x, int p) {
    pos[x] = euler.size();
    euler.push_back(x);
    for (auto [y, z] : adj[x]) {
        if (y == p) continue;
        dep[y] = dep[x] + 1;
        d2r[y] = d2r[x] + z;
        dfs(y, x);
        euler.push_back(x);
    }
}
int f(int i, int j) {
    return (i != -1 && (j == -1 || dep[i] < dep[j])) ? i : j;
}
void build() {
    int n = euler.size();
    s.resize(lg[n] + 1);
    s[0] = euler;
    for (int i = 0; i < lg[n]; i++) {
        s[i + 1].resize(n - (2 << i) + 1);
        for (int j = 0; j + (2 << i) <= n; j++) {
            s[i + 1][j] = f(s[i][j], s[i][j + (1 << i)]);
        }
    }
}
int lca(int a, int b) {
    a = pos[a], b = pos[b];
    if (a > b) swap(a, b); b++;
    int k = lg[b - a];
    return f(s[k][a], s[k][b - (1 << k)]);
}
ll dis(int a, int b) {
    return d2r[a] + d2r[b] - 2 * d2r[lca(a, b)];
}
void init(int x, int p) {
    sz[x] = 1;
    for (auto [y, z] : adj[x]) {
        if (y == p || vis[y]) continue;
        init(y, x);
        sz[x] += sz[y];
    }
}
int find(int x, int p, int n) {
    for (auto [y, z] : adj[x]) {
        if (y == p || vis[y]) continue;
        if (sz[y] * 2 > n) return find(y, x, n);
    }
    return x;
}
int cd(int x) {
    init(x, -1);
    vis[x = find(x, -1, sz[x])] = 1;
    for (auto [y, z] : adj[x]) {
        if (!vis[y]) par[cd(y)] = x;
    }
    return x;
}
void Init(int n, int A[], int B[], int D[]) {
    N = n;
    sz.resize(N);
    adj.resize(N);
    dep.resize(N);
    pos.resize(N);
    d2r.resize(N);
    vis.resize(N);
    par.resize(N);
    best.resize(N, 1e18);
    lg.resize(2 * N);
    for (int i = 2; i < 2 * N; i++) lg[i] = lg[i / 2] + 1;
    for (int i = 0; i < N - 1; i++) {
        adj[A[i]].emplace_back(B[i], D[i]);
        adj[B[i]].emplace_back(A[i], D[i]);
    }
    dfs(0, -1);
    build();
    par[cd(0)] = -1;
}
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 = par[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 = par[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 = par[j]) {
            best[j] = 1e18;
        }
    }
    return ans;
}

Compilation message

factories.cpp: In function 'int lca(int, int)':
factories.cpp:37:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   37 |     if (a > b) swap(a, b); b++;
      |     ^~
factories.cpp:37:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   37 |     if (a > b) swap(a, b); b++;
      |                            ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16988 KB Output is correct
2 Correct 213 ms 31420 KB Output is correct
3 Correct 257 ms 31544 KB Output is correct
4 Correct 262 ms 31408 KB Output is correct
5 Correct 306 ms 31540 KB Output is correct
6 Correct 121 ms 31312 KB Output is correct
7 Correct 254 ms 31412 KB Output is correct
8 Correct 270 ms 31316 KB Output is correct
9 Correct 329 ms 31680 KB Output is correct
10 Correct 132 ms 31292 KB Output is correct
11 Correct 259 ms 31508 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16988 KB Output is correct
2 Correct 944 ms 172288 KB Output is correct
3 Correct 1163 ms 174276 KB Output is correct
4 Correct 319 ms 172740 KB Output is correct
5 Correct 1595 ms 196540 KB Output is correct
6 Correct 1188 ms 175368 KB Output is correct
7 Correct 701 ms 60344 KB Output is correct
8 Correct 213 ms 60236 KB Output is correct
9 Correct 810 ms 63204 KB Output is correct
10 Correct 740 ms 60872 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16988 KB Output is correct
2 Correct 213 ms 31420 KB Output is correct
3 Correct 257 ms 31544 KB Output is correct
4 Correct 262 ms 31408 KB Output is correct
5 Correct 306 ms 31540 KB Output is correct
6 Correct 121 ms 31312 KB Output is correct
7 Correct 254 ms 31412 KB Output is correct
8 Correct 270 ms 31316 KB Output is correct
9 Correct 329 ms 31680 KB Output is correct
10 Correct 132 ms 31292 KB Output is correct
11 Correct 259 ms 31508 KB Output is correct
12 Correct 2 ms 16988 KB Output is correct
13 Correct 944 ms 172288 KB Output is correct
14 Correct 1163 ms 174276 KB Output is correct
15 Correct 319 ms 172740 KB Output is correct
16 Correct 1595 ms 196540 KB Output is correct
17 Correct 1188 ms 175368 KB Output is correct
18 Correct 701 ms 60344 KB Output is correct
19 Correct 213 ms 60236 KB Output is correct
20 Correct 810 ms 63204 KB Output is correct
21 Correct 740 ms 60872 KB Output is correct
22 Correct 1223 ms 177088 KB Output is correct
23 Correct 1348 ms 178308 KB Output is correct
24 Correct 1753 ms 179040 KB Output is correct
25 Correct 1798 ms 181452 KB Output is correct
26 Correct 1795 ms 179308 KB Output is correct
27 Correct 2281 ms 196760 KB Output is correct
28 Correct 443 ms 179220 KB Output is correct
29 Correct 1912 ms 179252 KB Output is correct
30 Correct 1905 ms 178596 KB Output is correct
31 Correct 1835 ms 179100 KB Output is correct
32 Correct 812 ms 63696 KB Output is correct
33 Correct 210 ms 60396 KB Output is correct
34 Correct 528 ms 58656 KB Output is correct
35 Correct 491 ms 58820 KB Output is correct
36 Correct 694 ms 59336 KB Output is correct
37 Correct 671 ms 59340 KB Output is correct