Submission #469635

#	Time	Username	Problem	Language	Result	Execution time	Memory
469635		Lam_lai_cuoc_doi	Factories (JOI14_factories)	C++17	100 / 100	2672 ms	117680 KiB

factories

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <class T>
void read(T &x)
{
    x = 0;
    register int c;
    while ((c = getchar()) && (c > '9' || c < '0'))
        ;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

constexpr bool typetest = 0;
constexpr int N = 5e5 + 5;
constexpr ll Inf = 1e17 + 7;
struct Path
{
    int v, type;
    ll w;
} a[N];

int n, m, in[N], beg[N];
int cnt[N], en[N], l(0), par[N];
ll dep[N], ans;

vector<pair<int, ll>> adj[N];

void dfs(int v, int p = -1)
{
    cnt[v] = 1;

    for (auto i : adj[v])
        if (i.first != p)
        {
            par[i.first] = v;
            dep[i.first] = dep[v] + i.second;

            dfs(i.first, v);

            cnt[v] += cnt[i.first];
        }
}

void hld(int v)
{
    in[v] = l;
    if (!beg[in[v]])
        beg[in[v]] = v;

    pair<int, int> ans({0, 0});

    for (auto i : adj[v])
        if (i.first != par[v])
            ans = max(ans, make_pair(cnt[i.first], i.first));

    if (ans.first != 0)
    {
        hld(ans.second);
        for (auto i : adj[v])
            if (i.first != par[v] && i.first != ans.second)
            {
                ++l;
                hld(i.first);
            }
    }
}

void Init(int nn, int* a, int* b, int* d)
{
    n = nn;
    for (int i = 0; i < n - 1; ++i)
    {
        adj[a[i] + 1].emplace_back(b[i] + 1, d[i]);
        adj[b[i] + 1].emplace_back(a[i] + 1, d[i]);
    }
    l = 1;
    dfs(1);
    hld(1);
}

void GetPath(int v, int type)
{
    ll w = dep[v];
    while (v)
    {
        ++m;
        a[m].v = v;
        a[m].type = type;
        a[m].w = w;

        v = par[beg[in[v]]];
    }
}

void Cal(int x, int y)
{
    sort(a + x, a + y + 1, [&](const Path &a, const Path &b)
         { return dep[a.v] < dep[b.v]; });

    ll minn[2] = {Inf, Inf};

    for (int i = y; i >= x; --i)
    {
        ans = min(ans, a[i].w + minn[a[i].type ^ 1] - 2 * dep[a[i].v]);
        minn[a[i].type] = min(minn[a[i].type], a[i].w);
    }
}

ll Query(int s, int* u, int t, int* v)
{
    m = 0;
    ans = Inf;

    for (int i = 0; i < s; ++i)
        GetPath(u[i] + 1, 1);
    for (int i = 0; i < t; ++i)
        GetPath(v[i] + 1, 0);

    sort(a + 1, a + m + 1, [&](const Path &a, const Path &b)
         { return in[a.v] < in[b.v]; });

    for (int i = 1, j = 1; i <= m; ++i)
    {
        while (j <= m && in[a[i].v] == in[a[j].v])
            ++j;
        Cal(i, j - 1);
        i = j - 1;
    }

    return ans;
}

Compilation message (stderr)

factories.cpp: In function 'void read(T&)':
factories.cpp:12:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   12 |     register int c;
      |                  ^

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