oj.uz

Submission #1044689

# Submission time Handle Problem Language Result Execution time Memory
1044689 2024-08-05T12:26:09 Z june0501 Factories (JOI14_factories) C++17
100 / 100
 1935 ms 299432 KB 
#include <bits/stdc++.h>
//#pragma GCC target("avx2")
//#pragma GCC optimize("O3,unroll-loops")
#define fastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
using namespace std;
using ll [[maybe_unused]] = long long;
using ull [[maybe_unused]] = unsigned long long;
using lll [[maybe_unused]] = __int128;
using lld [[maybe_unused]] = long double;
using llld [[maybe_unused]] = __float128;
template<typename T> using graph [[maybe_unused]] = vector<vector<pair<int,T>>>;
template<typename T> using matrix [[maybe_unused]] = vector<vector<T>>;
 
const ll INF = 0x3f3f3f3f3f3f3f3f;
/**
 * @brief Centroid Tree implementation
 */
class CentroidTree {
    int n, root;
    int MAX_BIT;
    graph<int> g;
    vector<int> sz,    // size of the subtree
                depth, // depth of the node
                tree,  // centroid tree(tree[i] = parent of i at the centroid tree)
                S, T, E;  // Euler Tour
    vector<ll> dist;  // distance from the initial root
 
    int pw = 0;
    int dfs(int u, int p) {
        sz[u] = 1;
        E[++pw] = u;
        S[u] = pw;
        for (const auto& [v, w]: g[u]) {
            if (v == p) continue;
            depth[v] = depth[u] + 1;
            dist[v] = dist[u] + w;
            sz[u] += dfs(v, u);
            E[++pw] = u;
        }
        return sz[u];
    }
 
    vector<int> pw2, lg2;
    vector<vector<pair<int,int>>> ST;
    void lca_prepare(){
        pw2.resize(MAX_BIT);
        pw2[0] = 1;
        for (int i = 1; i < MAX_BIT; i++) pw2[i] = pw2[i - 1] << 1;
 
        lg2.resize(n * 2);
        fill(lg2.begin(), lg2.end(), -1);
        for (int i = 0; i < MAX_BIT; i++) if (pw2[i] < n * 2) lg2[pw2[i]] = i;
        for (int i = 1; i < n * 2; i++) if (lg2[i] == -1) lg2[i] = lg2[i - 1];
 
        ST.resize(MAX_BIT, vector<pair<int,int>>(n * 2));
        for (int i = 1; i < n * 2; i++) ST[0][i] = {depth[E[i]], E[i]};
 
        for(int k = 1; k < MAX_BIT; k++) {
            for (int i = 1; i < n * 2; i++) {
                if (i + pw2[k - 1] > n * 2) continue;
                ST[k][i] = min(ST[k - 1][i], ST[k - 1][i + pw2[k - 1]]);
            }
        }
    }
 
    int lca(int u, int v) {
        int l = S[u], r = S[v];
        if (l > r) swap(l, r);
        int k = lg2[r - l + 1];
        return min(ST[k][l], ST[k][r - pw2[k] + 1]).second;
    }
 
    ll get_dist(int u, int v) {
        return dist[u] + dist[v] - 2 * dist[lca(u, v)];
    }
 
    int get_centroid(int u) {
        for (const auto& [v, w]: g[u]) {
            if (sz[u] >> 1 < sz[v] && sz[v] < sz[u]) {
                sz[u] -= sz[v];
                sz[v] += sz[u];
                return get_centroid(v);
            }
        }
        return u;
    }
 
    void build_centroid_tree(int u, int p = -1) {
        u = get_centroid(u);
 
        if (p == -1) tree[u] = u;
        else tree[u] = p;
 
        for (const auto& [v, _]: g[u])
            if (sz[v] < sz[u])
                build_centroid_tree(v, u);
    }
 
public:
    CentroidTree() = default;
 
    explicit
    CentroidTree(const graph<int>& g, int root = 1) : g(g), n((int)g.size()), root(root) {
        sz.resize(n, 0);
        depth.resize(n, 0);
        dist.resize(n, 0);
        S.resize(n), T.resize(n), E.resize(n * 2);
        tree.resize(n);
        MAX_BIT = std::ceil(std::log2(n)) + 1;
 
        dfs(root, -1);
        lca_prepare();
        build_centroid_tree(root);
 
        x_dist.resize(n, INF);
    }
 
    vector<ll> x_dist;
    void update(int u) {
        for (int v = u;; v = tree[v]) {
            x_dist[v] = min(x_dist[v], get_dist(u, v));
 
            if (tree[v] == v) break;
        }
    }
    ll query(int u) {
        ll res = INF;
        for (int v = u;; v = tree[v]) {
            res = min(res, x_dist[v] + get_dist(u, v));
 
            if (tree[v] == v) break;
        }
        return res;
    }
 
    void clear(int u) {
        for (int v = u;; v = tree[v]) {
            x_dist[v] = INF;
 
            if (tree[v] == v) break;
        }
    }
}; // class CentroidTree
 
graph<int> g;
CentroidTree solver;
 
void Init(int N, int A[], int B[], int D[]) {
    g.resize(N + 1);
    for (int i = 0; i < N - 1; i++) {
        g[A[i]+1].emplace_back(B[i]+1, D[i]);
        g[B[i]+1].emplace_back(A[i]+1, D[i]);
    }
    solver = CentroidTree(g);
}
 
ll Query(int S, int X[], int T, int Y[]) {
    ll ans = INF;
    for (int i = 0; i < S; i++) solver.update(X[i]+1);
    for (int i = 0; i < T; i++) ans = min(ans, solver.query(Y[i]+1));
    for (int i = 0; i < S; i++) solver.clear(X[i]+1);
    return ans;
}

Compilation message

factories.cpp: In constructor 'CentroidTree::CentroidTree(graph<int>&, int)':
factories.cpp:24:16: warning: 'CentroidTree::g' will be initialized after [-Wreorder]
   24 |     graph<int> g;
      |                ^
factories.cpp:22:9: warning:   'int CentroidTree::n' [-Wreorder]
   22 |     int n, root;
      |         ^
factories.cpp:106:5: warning:   when initialized here [-Wreorder]
  106 |     CentroidTree(const graph<int>& g, int root = 1) : g(g), n((int)g.size()), root(root) {
      |     ^~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16988 KB Output is correct
2 Correct 244 ms 22968 KB Output is correct
3 Correct 324 ms 22864 KB Output is correct
4 Correct 305 ms 22868 KB Output is correct
5 Correct 328 ms 32564 KB Output is correct
6 Correct 132 ms 32340 KB Output is correct
7 Correct 317 ms 32340 KB Output is correct
8 Correct 322 ms 32336 KB Output is correct
9 Correct 313 ms 32536 KB Output is correct
10 Correct 132 ms 32448 KB Output is correct
11 Correct 310 ms 32320 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 851 ms 264816 KB Output is correct
3 Correct 964 ms 265448 KB Output is correct
4 Correct 435 ms 268220 KB Output is correct
5 Correct 1211 ms 278528 KB Output is correct
6 Correct 1068 ms 265676 KB Output is correct
7 Correct 731 ms 66868 KB Output is correct
8 Correct 224 ms 67792 KB Output is correct
9 Correct 747 ms 68776 KB Output is correct
10 Correct 731 ms 67300 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 244 ms 22968 KB Output is correct
3 Correct 324 ms 22864 KB Output is correct
4 Correct 305 ms 22868 KB Output is correct
5 Correct 328 ms 32564 KB Output is correct
6 Correct 132 ms 32340 KB Output is correct
7 Correct 317 ms 32340 KB Output is correct
8 Correct 322 ms 32336 KB Output is correct
9 Correct 313 ms 32536 KB Output is correct
10 Correct 132 ms 32448 KB Output is correct
11 Correct 310 ms 32320 KB Output is correct
12 Correct 3 ms 16984 KB Output is correct
13 Correct 851 ms 264816 KB Output is correct
14 Correct 964 ms 265448 KB Output is correct
15 Correct 435 ms 268220 KB Output is correct
16 Correct 1211 ms 278528 KB Output is correct
17 Correct 1068 ms 265676 KB Output is correct
18 Correct 731 ms 66868 KB Output is correct
19 Correct 224 ms 67792 KB Output is correct
20 Correct 747 ms 68776 KB Output is correct
21 Correct 731 ms 67300 KB Output is correct
22 Correct 1229 ms 288200 KB Output is correct
23 Correct 1555 ms 289420 KB Output is correct
24 Correct 1600 ms 288172 KB Output is correct
25 Correct 1740 ms 290416 KB Output is correct
26 Correct 1619 ms 288476 KB Output is correct
27 Correct 1935 ms 299432 KB Output is correct
28 Correct 553 ms 292916 KB Output is correct
29 Correct 1653 ms 288440 KB Output is correct
30 Correct 1641 ms 288092 KB Output is correct
31 Correct 1627 ms 288456 KB Output is correct
32 Correct 784 ms 83100 KB Output is correct
33 Correct 226 ms 82092 KB Output is correct
34 Correct 526 ms 79712 KB Output is correct
35 Correct 554 ms 79928 KB Output is correct
36 Correct 721 ms 79928 KB Output is correct
37 Correct 738 ms 79928 KB Output is correct