Submission #796437

#	Time	Username	Problem	Language	Result	Execution time	Memory
796437		finn__	Tourism (JOI23_tourism)	C++17	0 / 100	30 ms	18424 KiB

tourism

#include <bits/stdc++.h>
using namespace std;

template <typename T, size_t N>
struct fenwick_tree
{
    T t[N];

    void update(int64_t i, T x)
    {
        ++i;
        while (i <= N)
            t[i - 1] += x, i += i & -i;
    }

    T range_sum(int64_t i, int64_t j)
    {
        ++j;
        T x = 0;
        while (j)
            x += t[j - 1], j -= j & -j;
        while (i)
            x -= t[i - 1], i -= i & -i;
        return x;
    }

    void reset() { memset(t, 0, sizeof t); }
};

constexpr size_t N = 100001, LGN = 18;

fenwick_tree<size_t, N> tree;
vector<size_t> g[N];
size_t nxt[N], last[N], c[LGN][N], anc[N][LGN];

vector<size_t> range_distinct_values(size_t n, size_t *seq, vector<tuple<size_t, size_t, size_t>> queries)
{
    tree.reset();
    fill(last, last + N, n);
    for (size_t i = n - 1; i < n; --i)
        if (seq[i] != SIZE_MAX)
        {
            nxt[i] = last[seq[i]];
            last[seq[i]] = i;
        }

    sort(queries.begin(), queries.end());

    for (size_t i = 0; i < N; ++i)
        tree.update(last[i], 1);
    size_t l = 0;
    vector<size_t> ans(queries.size());
    for (auto const &[a, b, i] : queries)
    {
        while (l < a)
        {
            if (seq[l] != SIZE_MAX)
                tree.update(nxt[l], 1);
            ++l;
        }
        ans[i] = tree.range_sum(a, b);
    }

    return ans;
}

vector<size_t> fill_anc_array(size_t u, size_t p = -1, size_t d = 0)
{
    assert(d < LGN);
    vector<size_t> subtree = {u};
    for (auto const &v : g[u])
        if (v != p)
        {
            auto y = fill_anc_array(v, u, d + 1);
            subtree.insert(subtree.end(), y.begin(), y.end());
        }
    for (auto const &v : subtree)
        anc[d][v] = u;
    return subtree;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    size_t n, m, q;
    cin >> n >> m >> q;
    for (size_t i = 0; i < n - 1; ++i)
    {
        size_t u, v;
        cin >> u >> v;
        g[u - 1].push_back(v - 1);
        g[v - 1].push_back(u - 1);
    }

    memset(anc, 255, sizeof anc);
    fill_anc_array(0);

    for (size_t i = 0; i < m; ++i)
    {
        size_t u;
        cin >> u;
        for (size_t j = 0; j < LGN; ++j)
            c[j][i] = anc[u][j];
    }

    vector<tuple<size_t, size_t, size_t>> queries;
    for (size_t i = 0; i < q; ++i)
    {
        size_t a, b;
        cin >> a >> b;
        queries.emplace_back(a, b, i);
    }

    vector<size_t> ans(q);
    vector<bool> finished(q);
    for (size_t i = LGN - 1; i < LGN; --i)
    {
        auto z = range_distinct_values(m, c[i], queries);
        for (size_t i = 0; i < q; ++i)
        {
            ans[i] += z[i] - finished[i];
            finished[i] = z[i] == 1;
        }
    }

    for (auto const &x : ans)
        cout << x << '\n';
}

Compilation message (stderr)

tourism.cpp: In instantiation of 'void fenwick_tree<T, N>::update(int64_t, T) [with T = long unsigned int; long unsigned int N = 100001; int64_t = long int]':
tourism.cpp:50:31:   required from here
tourism.cpp:12:18: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'long unsigned int' [-Wsign-compare]
   12 |         while (i <= N)
      |                ~~^~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 41