oj.uz

Submission #387824

# Submission time Handle Problem Language Result Execution time Memory
387824 2021-04-09T08:58:31 Z arujbansal Factories (JOI14_factories) C++17
100 / 100
 6249 ms 363620 KB 
#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;

const int MXN = 5e5 + 1, MXK = 19;
const ll INF = 1e18;
vector<pair<int, ll>> g[MXN], par[MXN];
int subtree[MXN];
bool vis[MXN];
ll best[MXN];

void dfs1(int u, int p) {
    subtree[u] = 1;

    for (const auto &[v, w] : g[u]) {
        if (v == p) continue;

        dfs1(v, u);
        subtree[u] += subtree[v];
    }
}

void dfs2(int u, int p, int cur_centroid, ll cur_dist) {
    par[u].emplace_back(cur_centroid, cur_dist);

    for (const auto &[v, w] : g[u]) {
        if (v == p || vis[v]) continue;
        dfs2(v, u, cur_centroid, cur_dist + w);
    }
}

int centroid(int u, int p, int vertices) {
    if (p != -1) {
        subtree[p] -= subtree[u];
        subtree[u] += subtree[p];
    }

    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 c = centroid(u, -1, subtree[u]);

    if (p == -1)
        p = c;

    dfs2(c, -1, c, 0);
    vis[c] = true;

    for (const auto &[v, w] : g[c]) {
        if (vis[v]) continue;
        build_cd(v, c);
    }
}

void build_factory(int u) {
    best[u] = 0;

    for (const auto &[p, d] : par[u])
        best[p] = min(best[p], d);
}

void remove_factory(int u) {
    best[u] = INF;

    for (const auto &[p, d] : par[u])
        best[p] = INF;
}

ll query_factory(int u) {
    ll ans = best[u];

    for (const auto &[p, d] : par[u])
        ans = min(ans, best[p] + d);

    return ans;
}

void Init(int N, int A[], int B[], int D[]) {
    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]);
    }

    dfs1(0, -1);
    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;
}

#ifdef local
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();
}
#endif

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24172 KB Output is correct
2 Correct 379 ms 32932 KB Output is correct
3 Correct 415 ms 33476 KB Output is correct
4 Correct 413 ms 33480 KB Output is correct
5 Correct 449 ms 33744 KB Output is correct
6 Correct 310 ms 32360 KB Output is correct
7 Correct 404 ms 33344 KB Output is correct
8 Correct 406 ms 33404 KB Output is correct
9 Correct 440 ms 33844 KB Output is correct
10 Correct 310 ms 32452 KB Output is correct
11 Correct 401 ms 33372 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24012 KB Output is correct
2 Correct 2923 ms 195676 KB Output is correct
3 Correct 3981 ms 266432 KB Output is correct
4 Correct 1301 ms 107456 KB Output is correct
5 Correct 4930 ms 359348 KB Output is correct
6 Correct 4295 ms 285328 KB Output is correct
7 Correct 1501 ms 69044 KB Output is correct
8 Correct 737 ms 45936 KB Output is correct
9 Correct 1677 ms 81408 KB Output is correct
10 Correct 1502 ms 70132 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24172 KB Output is correct
2 Correct 379 ms 32932 KB Output is correct
3 Correct 415 ms 33476 KB Output is correct
4 Correct 413 ms 33480 KB Output is correct
5 Correct 449 ms 33744 KB Output is correct
6 Correct 310 ms 32360 KB Output is correct
7 Correct 404 ms 33344 KB Output is correct
8 Correct 406 ms 33404 KB Output is correct
9 Correct 440 ms 33844 KB Output is correct
10 Correct 310 ms 32452 KB Output is correct
11 Correct 401 ms 33372 KB Output is correct
12 Correct 18 ms 24012 KB Output is correct
13 Correct 2923 ms 195676 KB Output is correct
14 Correct 3981 ms 266432 KB Output is correct
15 Correct 1301 ms 107456 KB Output is correct
16 Correct 4930 ms 359348 KB Output is correct
17 Correct 4295 ms 285328 KB Output is correct
18 Correct 1501 ms 69044 KB Output is correct
19 Correct 737 ms 45936 KB Output is correct
20 Correct 1677 ms 81408 KB Output is correct
21 Correct 1502 ms 70132 KB Output is correct
22 Correct 4033 ms 219024 KB Output is correct
23 Correct 4011 ms 224296 KB Output is correct
24 Correct 5217 ms 291648 KB Output is correct
25 Correct 5210 ms 295788 KB Output is correct
26 Correct 5167 ms 292684 KB Output is correct
27 Correct 6249 ms 363620 KB Output is correct
28 Correct 1899 ms 93736 KB Output is correct
29 Correct 4962 ms 267856 KB Output is correct
30 Correct 5172 ms 267544 KB Output is correct
31 Correct 5095 ms 268044 KB Output is correct
32 Correct 1940 ms 82472 KB Output is correct
33 Correct 771 ms 46432 KB Output is correct
34 Correct 1357 ms 61776 KB Output is correct
35 Correct 1323 ms 62488 KB Output is correct
36 Correct 1508 ms 67516 KB Output is correct
37 Correct 1694 ms 67668 KB Output is correct