oj.uz

Submission #469635

# Submission time Handle Problem Language Result Execution time Memory
469635 2021-09-01T13:54:14 Z Lam_lai_cuoc_doi Factories (JOI14_factories) C++17
100 / 100
 2672 ms 117680 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 12492 KB Output is correct
2 Correct 900 ms 28600 KB Output is correct
3 Correct 717 ms 28380 KB Output is correct
4 Correct 761 ms 28612 KB Output is correct
5 Correct 438 ms 28868 KB Output is correct
6 Correct 494 ms 28484 KB Output is correct
7 Correct 710 ms 28372 KB Output is correct
8 Correct 720 ms 28572 KB Output is correct
9 Correct 431 ms 28732 KB Output is correct
10 Correct 499 ms 28332 KB Output is correct
11 Correct 714 ms 28268 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12236 KB Output is correct
2 Correct 1551 ms 61764 KB Output is correct
3 Correct 1144 ms 65272 KB Output is correct
4 Correct 757 ms 60240 KB Output is correct
5 Correct 1037 ms 95192 KB Output is correct
6 Correct 1217 ms 66512 KB Output is correct
7 Correct 765 ms 44500 KB Output is correct
8 Correct 533 ms 44572 KB Output is correct
9 Correct 562 ms 49048 KB Output is correct
10 Correct 819 ms 45964 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 12492 KB Output is correct
2 Correct 900 ms 28600 KB Output is correct
3 Correct 717 ms 28380 KB Output is correct
4 Correct 761 ms 28612 KB Output is correct
5 Correct 438 ms 28868 KB Output is correct
6 Correct 494 ms 28484 KB Output is correct
7 Correct 710 ms 28372 KB Output is correct
8 Correct 720 ms 28572 KB Output is correct
9 Correct 431 ms 28732 KB Output is correct
10 Correct 499 ms 28332 KB Output is correct
11 Correct 714 ms 28268 KB Output is correct
12 Correct 9 ms 12236 KB Output is correct
13 Correct 1551 ms 61764 KB Output is correct
14 Correct 1144 ms 65272 KB Output is correct
15 Correct 757 ms 60240 KB Output is correct
16 Correct 1037 ms 95192 KB Output is correct
17 Correct 1217 ms 66512 KB Output is correct
18 Correct 765 ms 44500 KB Output is correct
19 Correct 533 ms 44572 KB Output is correct
20 Correct 562 ms 49048 KB Output is correct
21 Correct 819 ms 45964 KB Output is correct
22 Correct 2672 ms 75920 KB Output is correct
23 Correct 2434 ms 97248 KB Output is correct
24 Correct 2033 ms 94588 KB Output is correct
25 Correct 1896 ms 98320 KB Output is correct
26 Correct 1773 ms 91136 KB Output is correct
27 Correct 1413 ms 117680 KB Output is correct
28 Correct 1285 ms 91596 KB Output is correct
29 Correct 1713 ms 90732 KB Output is correct
30 Correct 1726 ms 89988 KB Output is correct
31 Correct 1771 ms 90728 KB Output is correct
32 Correct 696 ms 51944 KB Output is correct
33 Correct 702 ms 47744 KB Output is correct
34 Correct 1395 ms 42204 KB Output is correct
35 Correct 1380 ms 42184 KB Output is correct
36 Correct 970 ms 42972 KB Output is correct
37 Correct 933 ms 42916 KB Output is correct