oj.uz

Submission #796462

# Submission time Handle Problem Language Result Execution time Memory
796462 2023-07-28T12:07:58 Z finn__ Tourism (JOI23_tourism) C++17
24 / 100
 335 ms 67352 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 = 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], 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 = 100001; 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 42 ms 32412 KB Output is correct
2 Incorrect 47 ms 32408 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 32412 KB Output is correct
2 Incorrect 47 ms 32408 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 32320 KB Output is correct
2 Runtime error 53 ms 67352 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 32308 KB Output is correct
2 Correct 33 ms 32468 KB Output is correct
3 Correct 32 ms 32732 KB Output is correct
4 Correct 306 ms 56972 KB Output is correct
5 Correct 278 ms 55724 KB Output is correct
6 Correct 318 ms 58684 KB Output is correct
7 Correct 335 ms 60172 KB Output is correct
8 Correct 334 ms 60060 KB Output is correct
9 Correct 329 ms 60092 KB Output is correct
10 Correct 320 ms 60140 KB Output is correct
11 Correct 325 ms 60364 KB Output is correct
12 Correct 326 ms 60064 KB Output is correct
13 Correct 318 ms 60160 KB Output is correct
14 Correct 261 ms 54212 KB Output is correct

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 32412 KB Output is correct
2 Incorrect 47 ms 32408 KB Output isn't correct
3 Halted 0 ms 0 KB -