oj.uz

Submission #821814

# Submission time Handle Problem Language Result Execution time Memory
821814 2023-08-11T17:54:09 Z PanosPask Factories (JOI14_factories) C++14
100 / 100
 3636 ms 352172 KB 
#include "factories.h"
#include "vector"
#include "math.h"
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long ll;

const ll INF = 1e18;

typedef pair<int, ll> pi;

int N;
vector<int> subtree_size;
vector<vector<pi>> adj_list;
vector<bool> removed;

// Ancestors in centroid tree(at most logN)
vector<vector<pi>> ancestors;
vector<ll> min_source_dist;

int calc_sb_size(int node, int par, ll d, int anc)
{
    subtree_size[node] = 1;

    for (auto [neigh, w] : adj_list[node]) {
        if (neigh != par && !removed[neigh]) {
            subtree_size[node] += calc_sb_size(neigh, node, d + w, anc);
        }
    }

    if (anc != -1)
        ancestors[node].pb(mp(anc, d));

    return subtree_size[node];
}

int find_centroid(int node, int par, int sz)
{
    for (auto [neigh, w] : adj_list[node]) {
        if (!removed[neigh] && neigh != par && subtree_size[neigh] > sz / 2)
            return find_centroid(neigh, node, sz);
    }

    return node;
}

void centroid_decompose(int node)
{
    int c = find_centroid(node, -1, subtree_size[node]);

    removed[c] = true;

    for (auto [neigh, w] : adj_list[c]) {
        if (removed[neigh])
            continue;

        calc_sb_size(neigh, -1, w, c);
    }

    for (auto [neigh, w] : adj_list[c]) {
        if (removed[neigh])
            continue;

        centroid_decompose(neigh);
    }

    return;
}

void Init(int n, int A[], int B[], int D[])
{
    N = n;

    adj_list.resize(N);
    subtree_size.resize(N);
    min_source_dist.assign(N, INF);
    removed.resize(N);
    ancestors.resize(N);

    for (int i = 0; i < N - 1; i++) {
        adj_list[A[i]].pb(mp(B[i], D[i]));
        adj_list[B[i]].pb(mp(A[i], D[i]));
    }

    calc_sb_size(0, -1, 0, -1);
    centroid_decompose(0);
}

long long Query(int S, int X[], int T, int Y[])
{
    removed.assign(N, false);

    ll res = INF;

    for (int i = 0; i < S; i++) {
        int v = X[i];

        // Iterate over all ancestors of v
        min_source_dist[v] = 0;
        for (auto [u, d] : ancestors[v]) {
            min_source_dist[u] = min(min_source_dist[u], d);
        }
    }

    for (int i = 0; i < T; i++) {
        int v = Y[i];

        res = min(res, min_source_dist[v]);
        for (auto [u, d] : ancestors[v]) {
            res = min(res, d + min_source_dist[u]);
        }
    }

    for (int i = 0; i < S; i++) {
        int v = X[i];

        min_source_dist[v] = INF;
        for (auto [u, d] : ancestors[v])
            min_source_dist[u] = INF;
    }

    return res;
}

Compilation message

factories.cpp: In function 'int calc_sb_size(int, int, ll, int)':
factories.cpp:28:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   28 |     for (auto [neigh, w] : adj_list[node]) {
      |               ^
factories.cpp: In function 'int find_centroid(int, int, int)':
factories.cpp:42:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |     for (auto [neigh, w] : adj_list[node]) {
      |               ^
factories.cpp: In function 'void centroid_decompose(int)':
factories.cpp:56:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |     for (auto [neigh, w] : adj_list[c]) {
      |               ^
factories.cpp:63:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   63 |     for (auto [neigh, w] : adj_list[c]) {
      |               ^
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:103:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  103 |         for (auto [u, d] : ancestors[v]) {
      |                   ^
factories.cpp:112:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  112 |         for (auto [u, d] : ancestors[v]) {
      |                   ^
factories.cpp:121:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  121 |         for (auto [u, d] : ancestors[v])
      |                   ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 596 KB Output is correct
2 Correct 178 ms 9488 KB Output is correct
3 Correct 192 ms 9932 KB Output is correct
4 Correct 201 ms 9988 KB Output is correct
5 Correct 201 ms 10704 KB Output is correct
6 Correct 138 ms 8932 KB Output is correct
7 Correct 190 ms 9920 KB Output is correct
8 Correct 196 ms 10164 KB Output is correct
9 Correct 202 ms 10672 KB Output is correct
10 Correct 137 ms 9036 KB Output is correct
11 Correct 190 ms 9916 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1673 ms 185120 KB Output is correct
3 Correct 2408 ms 235500 KB Output is correct
4 Correct 594 ms 82640 KB Output is correct
5 Correct 3150 ms 352172 KB Output is correct
6 Correct 2587 ms 235992 KB Output is correct
7 Correct 691 ms 54200 KB Output is correct
8 Correct 228 ms 29124 KB Output is correct
9 Correct 892 ms 60652 KB Output is correct
10 Correct 743 ms 55224 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 596 KB Output is correct
2 Correct 178 ms 9488 KB Output is correct
3 Correct 192 ms 9932 KB Output is correct
4 Correct 201 ms 9988 KB Output is correct
5 Correct 201 ms 10704 KB Output is correct
6 Correct 138 ms 8932 KB Output is correct
7 Correct 190 ms 9920 KB Output is correct
8 Correct 196 ms 10164 KB Output is correct
9 Correct 202 ms 10672 KB Output is correct
10 Correct 137 ms 9036 KB Output is correct
11 Correct 190 ms 9916 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1673 ms 185120 KB Output is correct
14 Correct 2408 ms 235500 KB Output is correct
15 Correct 594 ms 82640 KB Output is correct
16 Correct 3150 ms 352172 KB Output is correct
17 Correct 2587 ms 235992 KB Output is correct
18 Correct 691 ms 54200 KB Output is correct
19 Correct 228 ms 29124 KB Output is correct
20 Correct 892 ms 60652 KB Output is correct
21 Correct 743 ms 55224 KB Output is correct
22 Correct 2101 ms 185016 KB Output is correct
23 Correct 2222 ms 191608 KB Output is correct
24 Correct 3081 ms 235964 KB Output is correct
25 Correct 3111 ms 240280 KB Output is correct
26 Correct 2747 ms 237544 KB Output is correct
27 Correct 3636 ms 344620 KB Output is correct
28 Correct 721 ms 86736 KB Output is correct
29 Correct 2833 ms 236436 KB Output is correct
30 Correct 2934 ms 235404 KB Output is correct
31 Correct 2912 ms 236268 KB Output is correct
32 Correct 941 ms 62428 KB Output is correct
33 Correct 240 ms 29836 KB Output is correct
34 Correct 487 ms 43576 KB Output is correct
35 Correct 503 ms 44556 KB Output is correct
36 Correct 727 ms 52884 KB Output is correct
37 Correct 729 ms 52772 KB Output is correct