oj.uz

Submission #780632

# Submission time Handle Problem Language Result Execution time Memory
780632 2023-07-12T11:04:56 Z DuCanh2912 Factories (JOI14_factories) C++17
0 / 100
 39 ms 852 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); }

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

const u64 bs = 32;

class Sparse
{
protected:
    AdjList adj;
    std::vector<u64> tin, tout, dist;
    std::unordered_map<u64, u64, custom_hash> tour;
    u64 timer = 0;
    std::array<std::array<u64, 1000005>, bs> tb;

    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);
        tin.assign(n, 0);
        tout.assign(n, 0);
        dist.assign(n, 0);
    }
    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, limits<u64>::max());
    inst.build();
}

long long Query(int S, int X[], int T, int Y[])
{
    std::unordered_map<i64, i64, custom_hash> r1, r2, r3;
    std::vector<int> ord;
    int sz = S + T;
    ord.reserve(sz);

    for (int i = 0; i < S; i++)
    {
        r1[X[i]] = 0;
        r2[X[i]] = INF;
        r3[X[i]] = 0;
        ord.push_back(X[i]);
    }
    for (int i = 0; i < T; i++)
    {
        if (r1.find(Y[i]) != r1.end())
        {
            return 0;
        }
        r1[Y[i]] = 1;
        r2[Y[i]] = 0;
        r3[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 (r1.find(c) == r1.end())
        {
            r1[c] = 2;
            r2[c] = r3[c] = INF;
            ord.push_back(c);
        }
    }

    ord.resize(std::unique(ord.begin(), ord.end()) - ord.begin());
    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);
                r2[u] = std::min<i64>(r2[u], r2[v] + w);
                r3[u] = std::min<i64>(r3[u], r3[v] + w);
            }
        }
    };

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

    i64 res = INF;

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

    return res;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 852 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 852 KB Output isn't correct
2 Halted 0 ms 0 KB -