Submission #469634

#	Time	Username	Problem	Language	Result	Execution time	Memory
469634		Lam_lai_cuoc_doi	Factories (JOI14_factories)	C++17	Compilation error	0 ms	0 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;
}

void Read()
{
    int n, q;
    vector<int> a, b, d;
    cin >> n >> q;
    for (int i = 1; i < n; ++i)
    {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        a.emplace_back(u);
        b.emplace_back(v);
        d.emplace_back(w);
    }
    Init(n, a, b, d);
    while (q--)
    {
        int s, t;
        cin >> s >> t;
        vector<int> x(s), y(t);
        for (auto &j : x)
            cin >> j;
        for (auto &j : y)
            cin >> j;

        cout << Query(s, x, t, y) << "\n";
    }
}

void Solve()
{
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        //cout << "Case #" << _ << ": ";
        Read();
        Solve();
    }
    //cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}

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;
      |                  ^
factories.cpp: In function 'void Read()':
factories.cpp:153:13: error: cannot convert 'std::vector<int>' to 'int*'
  153 |     Init(n, a, b, d);
      |             ^
      |             |
      |             std::vector<int>
factories.cpp:74:24: note:   initializing argument 2 of 'void Init(int, int*, int*, int*)'
   74 | void Init(int nn, int* a, int* b, int* d)
      |                   ~~~~~^
factories.cpp:164:26: error: cannot convert 'std::vector<int>' to 'int*'
  164 |         cout << Query(s, x, t, y) << "\n";
      |                          ^
      |                          |
      |                          std::vector<int>
factories.cpp:115:22: note:   initializing argument 2 of 'll Query(int, int*, int, int*)'
  115 | ll Query(int s, int* u, int t, int* v)
      |                 ~~~~~^