oj.uz

Submission #387811

# Submission time Handle Problem Language Result Execution time Memory
387811 2021-04-09T08:49:20 Z maksim1744 Factories (JOI14_factories) C++17
100 / 100
 7833 ms 205512 KB 
#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#pragma GCC optimize("unroll-loops")
#include "factories.h"
 
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <array>
#include <stack>
#include <queue>
#include <random>
#include <numeric>
#include <functional>
#include <chrono>
#include <utility>
#include <iomanip>
#include <assert.h>
 
using namespace std;
 
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
 
#define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define rng_seed(x) mt19937 rng(x)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
// #define int long long
 
using ll = long long;
 
struct LCA {
    int n, k;
    vector<vector<int>> adj;
    array<array<int, (int)1e6 + 20>, 21> sparse_table;
    vector<int> euler, first_occurrence;
    int timer;
    bool lca_built;
 
    LCA(int _n = 0) { 
        lca_built = false;
 
        if (_n > 0)
            init(_n);
    }
 
    void init(int _n) {
        lca_built = false;
 
        n = _n;
 
        adj.resize(n);
        for (int i = 0; i < n; i++)
            adj[i].clear();
 
        euler.clear();
        first_occurrence.resize(n);
        timer = 0;
    }
 
    void add_edge(int u, int v) {
        assert(n > 0);
 
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
 
    void run(int root = 0) {
        assert(n > 0);
 
        dfs(root, -1);
        build();
 
        lca_built = true;
    }
 
    void dfs(int u = 0, int p = -1) {
        first_occurrence[u] = timer++;
        euler.push_back(u);
 
        for (const auto &v : adj[u]) {
            if (v == p) continue;
            
            dfs(v, u);
            euler.push_back(u);
            timer++;
        }
    }
 
    void build() {
        k = 31 - __builtin_clz(timer) + 1;
 
        for (int j = 0; j < timer; j++)
            sparse_table[0][j] = euler[j];
 
        for (int i = 1; i < k; i++) {
            for (int j = 0; j + (1 << i) - 1 < timer; j++) {
                int x = sparse_table[i - 1][j];
                int y = sparse_table[i - 1][j + (1 << (i - 1))];
 
                sparse_table[i][j] = (first_occurrence[x] < first_occurrence[y] ? x : y);
            }
        }
    }
 
    int query(int u, int v) {
        assert(lca_built == true);
 
        int l = first_occurrence[u], r = first_occurrence[v];
        if (l > r)
            swap(l, r);

        int i = 31 - __builtin_clz(r - l + 1);
 
        int x = sparse_table[i][l], y = sparse_table[i][r - (1 << i) + 1];
        return first_occurrence[x] < first_occurrence[y] ? x : y;
    }
};
 
const int MXN = 5e5 + 1, MXK = 19;
const ll INF = 1e18;
vector<pair<int, ll>> g[MXN];
int cd_par[MXN], subtree[MXN];
bool vis[MXN];
ll dist_g[MXN], best[MXN];
LCA lca_g;
 
void dfs1(int u, int p, ll cur_dist) {
    dist_g[u] = cur_dist;
 
    for (const auto &[v, w] : g[u]) {
        if (v == p) continue;
        dfs1(v, u, cur_dist + w);
    }
}
 
ll dist(int u, int v) {
    if (u == v) return 0;
    int cur_lca = lca_g.query(u, v);
    return dist_g[u] - dist_g[cur_lca] + dist_g[v] - dist_g[cur_lca];
}
 
void dfs_subtree(int u, int p) {
    subtree[u] = 1;
 
    for (const auto &[v, w] : g[u]) {
        if (v == p || vis[v]) continue;
 
        dfs_subtree(v, u);
        subtree[u] += subtree[v];
    }
}
 
int centroid(int u, int p, int vertices) {
    for (const auto &[v, w] : g[u]) {
        if (v == p || vis[v]) continue;
 
        if (subtree[v] * 2 > vertices)
            return centroid(v, u, vertices);
    }
 
    return u;
}
 
void build_cd(int u, int p, int dep = 0) {
    assert(dep <= 22);
    dfs_subtree(u, -1);
    int c = centroid(u, -1, subtree[u]);
 
    if (p == -1)
        p = c;
 
    cd_par[c] = p;
    vis[c] = true;
 
    for (const auto &[v, w] : g[c]) {
        if (vis[v]) continue;
        build_cd(v, c, dep + 1);
    }
}
 
void build_factory(int u) {
    int v = u;
    best[v] = 0;
 
    do {
        v = cd_par[v];
        best[v] = min(best[v], dist(u, v));
    } while (v != cd_par[v]);
}
 
void remove_factory(int v) {
    best[v] = INF;
 
    do {
        v = cd_par[v];
        best[v] = INF;
    } while (v != cd_par[v]);
}
 
ll query_factory(int u) {
    int v = u;
    ll ans = best[v];
 
    do {
        v = cd_par[v];
        ans = min(ans, dist(u, v) + best[v]);
    } while (v != cd_par[v]);
 
    return ans;
}
 
void Init(int N, int A[], int B[], int D[]) {
    lca_g.init(N);
 
    for (int i = 0; i < N - 1; i++) {
        g[A[i]].emplace_back(B[i], D[i]);
        g[B[i]].emplace_back(A[i], D[i]);
 
        lca_g.add_edge(A[i], B[i]);
    }
 
    lca_g.run(0);
 
    dfs1(0, -1, 0);
    build_cd(0, -1);
 
    for (int i = 0; i <= N; i++)
        best[i] = INF;
}
 
ll Query(int S, int X[], int T, int Y[]) {
    ll ans = INF;
 
    for (int i = 0; i < S; i++)
        build_factory(X[i]);
 
    for (int i = 0; i < T; i++)
        ans = min(ans, query_factory(Y[i]));
 
    for (int i = 0; i < S; i++)
        remove_factory(X[i]);
 
    return ans;
}
 
// void solve() {
//     int N,  Q;
//     cin >> N >> Q;
 
//     int A[N - 1], B[N - 1], D[N - 1];
//     for (int i = 0; i < N - 1; i++)
//         cin >> A[i] >> B[i] >> D[i];
 
//     Init(N, A, B, D);
 
//     while (Q--) {
//         int S, T;
//         cin >> S >> T;
 
//         int X[S], Y[T];
//         for (int i = 0; i < S; i++)
//             cin >> X[i];
 
//         for (int i = 0; i < T; i++)
//             cin >> Y[i];
 
//         cout << Query(S, X, T, Y) << "\n";
//     }
// }
 
// signed main() {
//     ios_base::sync_with_stdio(false);
//     cin.tie(nullptr);
 
//     int TC = 1;
//     // cin >> TC;
//     while (TC--) solve();
// }

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12548 KB Output is correct
2 Correct 480 ms 21540 KB Output is correct
3 Correct 686 ms 21568 KB Output is correct
4 Correct 647 ms 21540 KB Output is correct
5 Correct 718 ms 21916 KB Output is correct
6 Correct 292 ms 21468 KB Output is correct
7 Correct 649 ms 21472 KB Output is correct
8 Correct 677 ms 21488 KB Output is correct
9 Correct 693 ms 21804 KB Output is correct
10 Correct 350 ms 21496 KB Output is correct
11 Correct 677 ms 21580 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 12356 KB Output is correct
2 Correct 3577 ms 170948 KB Output is correct
3 Correct 4675 ms 173032 KB Output is correct
4 Correct 1353 ms 173876 KB Output is correct
5 Correct 6394 ms 205512 KB Output is correct
6 Correct 4898 ms 174300 KB Output is correct
7 Correct 2337 ms 50764 KB Output is correct
8 Correct 492 ms 51972 KB Output is correct
9 Correct 2776 ms 55688 KB Output is correct
10 Correct 2374 ms 51936 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12548 KB Output is correct
2 Correct 480 ms 21540 KB Output is correct
3 Correct 686 ms 21568 KB Output is correct
4 Correct 647 ms 21540 KB Output is correct
5 Correct 718 ms 21916 KB Output is correct
6 Correct 292 ms 21468 KB Output is correct
7 Correct 649 ms 21472 KB Output is correct
8 Correct 677 ms 21488 KB Output is correct
9 Correct 693 ms 21804 KB Output is correct
10 Correct 350 ms 21496 KB Output is correct
11 Correct 677 ms 21580 KB Output is correct
12 Correct 35 ms 12356 KB Output is correct
13 Correct 3577 ms 170948 KB Output is correct
14 Correct 4675 ms 173032 KB Output is correct
15 Correct 1353 ms 173876 KB Output is correct
16 Correct 6394 ms 205512 KB Output is correct
17 Correct 4898 ms 174300 KB Output is correct
18 Correct 2337 ms 50764 KB Output is correct
19 Correct 492 ms 51972 KB Output is correct
20 Correct 2776 ms 55688 KB Output is correct
21 Correct 2374 ms 51936 KB Output is correct
22 Correct 5125 ms 172412 KB Output is correct
23 Correct 4721 ms 174752 KB Output is correct
24 Correct 6177 ms 174836 KB Output is correct
25 Correct 6387 ms 178400 KB Output is correct
26 Correct 6207 ms 175044 KB Output is correct
27 Correct 7833 ms 202288 KB Output is correct
28 Correct 1542 ms 177876 KB Output is correct
29 Correct 6152 ms 174572 KB Output is correct
30 Correct 6212 ms 173920 KB Output is correct
31 Correct 6157 ms 174624 KB Output is correct
32 Correct 2187 ms 56832 KB Output is correct
33 Correct 492 ms 52612 KB Output is correct
34 Correct 1539 ms 48840 KB Output is correct
35 Correct 1536 ms 48872 KB Output is correct
36 Correct 1993 ms 49568 KB Output is correct
37 Correct 2024 ms 49536 KB Output is correct