oj.uz

Submission #796461

# Submission time Handle Problem Language Result Execution time Memory
796461 2023-07-28T12:07:36 Z finn__ Tourism (JOI23_tourism) C++17
0 / 100
 5 ms 1356 KB 
#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 = 1001, 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], qans[N];
bitset<N> finished;

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[v][d] = 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);
    memset(c, 255, sizeof c);
    fill_anc_array(0);

    for (size_t i = 0; i < m; ++i)
    {
        size_t u;
        cin >> u, --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 - 1, b - 1, i);
    }

    vector<size_t> z[LGN];
    for (size_t i = LGN - 1; i < LGN; --i)
    {
        z[i] = range_distinct_values(m, c[i], queries);
    }
    for (size_t i = LGN - 1; i < LGN; --i)
    {
        for (size_t j = 0; j < q; ++j)
        {
            qans[j] += z[i][j] - finished[j];
            if (!finished[j])
            {
                finished[j] = 1;
                for (size_t k = i - 1; k < i; --k)
                    finished[j] = finished[j] && z[k][j] == 1;
            }
        }
    }

    for (size_t i = 0; i < q; ++i)
        cout << qans[i] + 1 << '\n';
}

Compilation message

tourism.cpp: In instantiation of 'void fenwick_tree<T, N>::update(int64_t, T) [with T = long unsigned int; long unsigned int N = 1001; int64_t = long int]':
tourism.cpp:51: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.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 608 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Runtime error 5 ms 1356 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

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