oj.uz

Submission #780801

# Submission time Handle Problem Language Result Execution time Memory
780801 2023-07-12T13:19:27 Z vjudge1 Factories (JOI14_factories) C++17
15 / 100
 8000 ms 228416 KB 
#include <bits/stdc++.h>

#pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")

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>;

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 500005
#define MAX_2N MAX_N * 2 + 5

const u64 bs = 32;

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

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

class Sparse
{
protected:
    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 euler(const AdjList &adj, 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(adj, 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 dfs_vtree(const AdjList &vtree, u64 u, u64 prev)
{
    for (auto &[v, w] : vtree[u])
    {
        if (v != prev)
        {
            dfs_vtree(vtree, v, u);
            r1[u] = std::min(r1[u], r1[v] + w);
            r2[u] = std::min(r2[u], r2[v] + w);
        }
    }
};

void Init(int _N, int A[], int B[], int D[])
{
    AdjList adj;
    N = _N;
    adj.resize(N);
    for (u64 i = 0; i < N - 1; ++i)
    {
        adj[A[i]].emplace_back(B[i], D[i]);
        adj[B[i]].emplace_back(A[i], D[i]);
    }
    inst.euler(adj, 0, UDEF);
    inst.build();
    rtype.fill(UDEF);
}

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

    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]] == 0)
        {
            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.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]);
    }

    dfs_vtree(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]]);
        rtype[ord[i]] = UDEF;
    }

    return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 4692 KB Output is correct
2 Correct 853 ms 13972 KB Output is correct
3 Correct 916 ms 13968 KB Output is correct
4 Correct 891 ms 14044 KB Output is correct
5 Correct 761 ms 14228 KB Output is correct
6 Correct 650 ms 13916 KB Output is correct
7 Correct 857 ms 13988 KB Output is correct
8 Correct 848 ms 14112 KB Output is correct
9 Correct 749 ms 14212 KB Output is correct
10 Correct 642 ms 13924 KB Output is correct
11 Correct 880 ms 14008 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4564 KB Output is correct
2 Execution timed out 8038 ms 228416 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 4692 KB Output is correct
2 Correct 853 ms 13972 KB Output is correct
3 Correct 916 ms 13968 KB Output is correct
4 Correct 891 ms 14044 KB Output is correct
5 Correct 761 ms 14228 KB Output is correct
6 Correct 650 ms 13916 KB Output is correct
7 Correct 857 ms 13988 KB Output is correct
8 Correct 848 ms 14112 KB Output is correct
9 Correct 749 ms 14212 KB Output is correct
10 Correct 642 ms 13924 KB Output is correct
11 Correct 880 ms 14008 KB Output is correct
12 Correct 4 ms 4564 KB Output is correct
13 Execution timed out 8038 ms 228416 KB Time limit exceeded
14 Halted 0 ms 0 KB -