oj.uz

Submission #780771

# Submission time Handle Problem Language Result Execution time Memory
780771 2023-07-12T12:54:04 Z vjudge1 Factories (JOI14_factories) C++17
15 / 100
 1038 ms 156160 KB 
#include <bits/stdc++.h>

typedef unsigned short u16;
typedef short i16;
typedef unsigned int u32;
typedef int i32;
typedef unsigned long long u64;
typedef long long i64;
typedef float f32;
typedef double f64;
typedef long double f80;
typedef long double f128;

template <typename T>
using limits = std::numeric_limits<T>;

struct custom_hash
{
    static u64 splitmix64(u64 x)
    {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    std::size_t operator()(u64 x) const
    {
        static const u64 rand_time = std::chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + rand_time);
    }
};

i32 lg2(u64 x) { return 8 * sizeof(u64) - __builtin_clzll(x) - 1; }

typedef std::vector<std::vector<std::pair<u64, u64>>> AdjList;

#define MAX_N 500000

const u64 bs = 32;

std::array<std::array<u64, MAX_N << 1>, bs> tb;
std::array<u64, MAX_N> rtype, r1, r2, tin, tout, dist, tour;

const u64 UDEF = limits<u64>::max();

class Sparse
{
protected:
    AdjList adj;
    u64 timer = 0;

    u64 min_dist(u64 a, u64 b) { return dist[a] < dist[b] ? a : b; }
    u64 get(u64 l, u64 r)
    {
        auto lg_len = lg2(r - l + 1);
        return min_dist(tb[lg_len][l], tb[lg_len][r - (1 << lg_len) + 1]);
    }

public:
    void init(u64 n)
    {
        adj.resize(n);
    }
    void add(int a, int b, int d)
    {
        adj[a].emplace_back(b, d);
        adj[b].emplace_back(a, d);
    }

    void euler(u64 u, u64 prev)
    {
        tin[u] = timer++;
        tour[timer] = u;
        for (auto &[v, w] : adj[u])
        {
            if (v != prev)
            {
                dist[v] = dist[u] + w;
                euler(v, u);
                tour[++timer] = u;
            }
        }
        tout[u] = timer;
    }

    void build()
    {
        for (u64 i = 1; i <= timer; ++i)
        {
            tb[0][i] = tour[i];
        }

        for (u64 i = 1; i < bs; ++i)
        {
            for (u64 j = 1; j + (1ULL << i) - 1 <= timer; ++j)
            {
                tb[i][j] = min_dist(tb[i - 1][j], tb[i - 1][j + (1ULL << (i - 1))]);
            }
        }
    }

    bool is_parent(u64 u, u64 v) { return tin[u] < tin[v] && tout[v] < tout[u]; }

    u64 lca(u64 u, u64 v)
    {
        if (is_parent(u, v))
        {
            return u;
        }
        if (is_parent(v, u))
        {
            return v;
        }
        if (tin[u] > tout[v])
        {
            return get(tout[v], tin[u]);
        }
        return get(tout[u], tin[v]);
    }

    u64 gtin(u64 x) { return tin[x]; }

    u64 gdist(u64 u, u64 v)
    {
        auto c = lca(u, v);
        return (dist[u] - dist[c]) + (dist[v] - dist[c]);
    }
};

Sparse inst;

const i64 INF = 1e18;
u64 N;

void Init(int _N, int A[], int B[], int D[])
{
    N = _N;
    inst.init(N);
    for (u64 i = 0; i < N - 1; ++i)
    {
        inst.add(A[i], B[i], D[i]);
    }
    inst.euler(0, UDEF);
    inst.build();
}

long long Query(int S, int X[], int T, int Y[])
{
    rtype.fill(UDEF);
    std::vector<int> ord;
    int sz = S + T;
    ord.reserve(sz);

    for (int i = 0; i < S; i++)
    {
        rtype[X[i]] = 0;
        r1[X[i]] = INF;
        r2[X[i]] = 0;
        ord.push_back(X[i]);
    }
    for (int i = 0; i < T; i++)
    {
        if (rtype[Y[i]] != UDEF)
        {
            return 0;
        }
        rtype[Y[i]] = 1;
        r1[Y[i]] = 0;
        r2[Y[i]] = INF;
        ord.push_back(Y[i]);
    }

    std::sort(ord.begin(), ord.end(), [](int a, int b) { return inst.gtin(a) < inst.gtin(b); });

    for (int i = 1; i < sz; ++i)
    {
        i64 c = inst.lca(ord[i], ord[i - 1]);
        if (rtype[c] == UDEF)
        {
            rtype[c] = 2;
            r1[c] = r2[c] = INF;
            ord.push_back(c);
        }
    }

    ord.erase(std::unique(ord.begin(), ord.end()), ord.end());
    std::sort(ord.begin(), ord.end(), [](int a, int b) { return inst.gtin(a) < inst.gtin(b); });

    AdjList vtree(N);
    std::stack<int> st;

    for (u64 i = 0; i < ord.size(); i++)
    {
        if (st.empty())
        {
            st.push(ord[i]);
            continue;
        }

        while (!st.empty() && !inst.is_parent(st.top(), ord[i]))
        {
            st.pop();
        }

        if (!st.empty())
        {
            vtree[st.top()].emplace_back(static_cast<u64>(ord[i]), inst.gdist(st.top(), ord[i]));
        }

        st.push(ord[i]);
    }

    std::function<void(u64, u64)> dfs_vtree = [&](u64 u, u64 prev)
    {
        for (auto &[v, w] : vtree[u])
        {
            if (v != prev)
            {
                dfs_vtree(v, u);
                r1[u] = std::min(r1[u], r1[v] + w);
                r2[u] = std::min(r2[u], r2[v] + w);
            }
        }
    };

    dfs_vtree(ord[0], limits<u64>::max());

    u64 res = INF;

    for (u64 i = 0; i < ord.size(); ++i)
    {
        res = std::min(res, r1[ord[i]] + r2[ord[i]]);
    }

    return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 4996 KB Output is correct
2 Correct 908 ms 23736 KB Output is correct
3 Correct 971 ms 23832 KB Output is correct
4 Correct 1038 ms 23892 KB Output is correct
5 Correct 851 ms 24056 KB Output is correct
6 Correct 754 ms 23696 KB Output is correct
7 Correct 960 ms 23724 KB Output is correct
8 Correct 951 ms 23920 KB Output is correct
9 Correct 856 ms 24056 KB Output is correct
10 Correct 747 ms 23692 KB Output is correct
11 Correct 964 ms 23832 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 4624 KB Output is correct
2 Runtime error 576 ms 156160 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 4996 KB Output is correct
2 Correct 908 ms 23736 KB Output is correct
3 Correct 971 ms 23832 KB Output is correct
4 Correct 1038 ms 23892 KB Output is correct
5 Correct 851 ms 24056 KB Output is correct
6 Correct 754 ms 23696 KB Output is correct
7 Correct 960 ms 23724 KB Output is correct
8 Correct 951 ms 23920 KB Output is correct
9 Correct 856 ms 24056 KB Output is correct
10 Correct 747 ms 23692 KB Output is correct
11 Correct 964 ms 23832 KB Output is correct
12 Correct 35 ms 4624 KB Output is correct
13 Runtime error 576 ms 156160 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -