Submission #694978

#	Time	Username	Problem	Language	Result	Execution time	Memory
694978		four_specks	Factories (JOI14_factories)	C++17	100 / 100	4505 ms	368072 KiB

factories

#include "factories.h"

#include <bits/stdc++.h>

using namespace std;

namespace
{
    vector<vector<pair<int, long>>> adj, gr;

    vector<int> sub;
    vector<bool> done;

    vector<long> dp;

} // namespace

int subtree(int u, int p)
{
    sub[u] = 1;
    for (auto [v, d] : adj[u])
    {
        if (v != p && !done[v])
            sub[u] += subtree(v, u);
    }

    return sub[u];
}

int get_centroid(int sz, int u, int p)
{
    for (auto [v, d] : adj[u])
    {
        if (v != p && !done[v])
        {
            if (sub[v] * 2 > sz)
                return get_centroid(sz, v, u);
        }
    }

    return u;
}

void dfs(int r, int u, int p, long dist)
{
    gr[u].emplace_back(r, dist);
    for (auto [v, d] : adj[u])
    {
        if (v != p && !done[v])
            dfs(r, v, u, dist + d);
    }
}

void rec(int u)
{
    int cen = get_centroid(subtree(u, -1), u, -1);

    dfs(cen, cen, -1, 0);

    done[cen] = 1;

    for (auto [v, d] : adj[cen])
    {
        if (!done[v])
            rec(v);
    }
}

void upd(int u)
{
    for (auto [r, dist] : gr[u])
        dp[r] = min(dp[r], dist);
}

long qry(int u)
{
    long x = LONG_MAX;
    for (auto [r, dist] : gr[u])
    {
        if (dp[r] != LONG_MAX)
            x = min(x, dist + dp[r]);
    }

    return x;
}

void reset(int u)
{
    for (auto [r, dist] : gr[u])
        dp[r] = LONG_MAX;
}

void Init(int N, int A[], int B[], int D[])
{
    adj.assign(N, vector<pair<int, long>>());
    for (int i = 0; i < N - 1; i++)
    {
        adj[A[i]].emplace_back(B[i], D[i]);
        adj[B[i]].emplace_back(A[i], D[i]);
    }

    sub.assign(N, 0);
    done.assign(N, 0);

    gr.assign(N, vector<pair<int, long>>());

    rec(0);

    dp.assign(N, LONG_MAX);
}

long long Query(int S, int X[], int T, int Y[])
{
    for (int i = 0; i < S; i++)
        upd(X[i]);

    long cost = LONG_MAX;
    for (int i = 0; i < T; i++)
        cost = min(cost, qry(Y[i]));

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

    return cost;
}

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