Submission #821812

#	Time	Username	Problem	Language	Result	Execution time	Memory
821812		PanosPask	Factories (JOI14_factories)	C++14	15 / 100	8012 ms	44276 KiB

factories

#include "factories.h"
#include "vector"
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long ll;

const ll INF = 1e18;

typedef pair<int, int> pi;

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

// Query dependent variables
// Minimum distance to a destination/source node
ll lc_min_dest, lc_min_source;
ll min_dest, min_source;
vector<bool> destination;
vector<bool> source;
ll ans;

int calc_sb_size(int node, int par, ll d)
{
    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);
        }
    }

    if (destination[node]) {
        ans = min(ans, d + min_source);
        lc_min_dest = min(lc_min_dest, d);
    }
    if (source[node]) {
        ans = min(ans, d + min_dest);
        lc_min_source = min(lc_min_source, 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]);

    min_dest = min_source = INF;

    removed[c] = true;
    if (destination[c])
        min_dest = 0;
    if (source[c])
        min_source = 0;

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

        lc_min_dest = lc_min_source = INF;
        calc_sb_size(neigh, -1, w);

        min_dest = min(min_dest, lc_min_dest);
        min_source = min(min_source, lc_min_source);
    }

    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);
    removed.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]));
    }
}

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

    for (int i = 0; i < S; i++)
        source[X[i]] = true;
    for (int i = 0; i < T; i++)
        destination[Y[i]] = true;

    ans = INF;
    min_dest = min_source = INF;
    calc_sb_size(0, -1, 0);
    centroid_decompose(0);

    return ans;
}

Compilation message (stderr)

factories.cpp: In function 'int calc_sb_size(int, int, ll)':
factories.cpp:31:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |     for (auto [neigh, w] : adj_list[node]) {
      |               ^
factories.cpp: In function 'int find_centroid(int, int, int)':
factories.cpp:51:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |     for (auto [neigh, w] : adj_list[node]) {
      |               ^
factories.cpp: In function 'void centroid_decompose(int)':
factories.cpp:71:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   71 |     for (auto [neigh, w] : adj_list[c]) {
      |               ^
factories.cpp:82:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   82 |     for (auto [neigh, w] : adj_list[c]) {
      |               ^

• Subtask 1: 15 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67