oj.uz

Submission #796482

# Submission time Handle Problem Language Result Execution time Memory
796482 2023-07-28T12:26:10 Z Johann Tourism (JOI23_tourism) C++14
24 / 100
 1271 ms 12664 KB 
#include "bits/stdc++.h"
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef tuple<int, int, int> tiii;
typedef vector<tiii> vtiii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

int N, M, Q;
vi C;
vvi adj;
vi cnt;
struct query
{
    int l, r, idx;
};
vector<query> queries;
int ans;
vi answers;

struct segtree
{
    vi arr;
    int size;
    int NEUTRAL = 0;
    int merge(int a, int b)
    {
        if (a == NEUTRAL || b == NEUTRAL)
            return max(a, b);
        while (a != b)
        {
            if (a < b)
                swap(a, b);
            a >>= 1;
        }
        return a;
    }
    void init(vi &A)
    {
        size = 1;
        while (size < sz(A))
            size *= 2;
        arr.assign(2 * size, NEUTRAL);

        for (int i = 0; i < sz(A); ++i)
            arr[i + size] = A[i];
        for (int i = size - 1; i > 0; --i)
            arr[i] = merge(arr[2 * i], arr[2 * i + 1]);
    }
    int query(int l, int r) { return query(l, r, 1, 0, size); }
    int query(int l, int r, int x, int lx, int rx)
    {
        if (l <= lx && rx <= r)
            return arr[x];
        if (r <= lx || rx <= l)
            return NEUTRAL;
        int m = (lx + rx) / 2;
        return merge(query(l, r, 2 * x, lx, m), query(l, r, 2 * x + 1, m, rx));
    }
};
segtree seglca;

void add(int x)
{
    while (x > 0)
    {
        ++cnt[x];
        if (cnt[x] == 1)
            ++ans;
        x >>= 1;
    }
}
void sub(int x)
{
    while (x > 0)
    {
        --cnt[x];
        if (cnt[x] == 0)
            --ans;
        x >>= 1;
    }
}

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

    cin >> N >> M >> Q;

    adj.resize(N);
    for (int i = 0, a, b; i < N - 1; ++i)
    {
        cin >> a >> b;
        --a, --b;
        adj[a].push_back(b), adj[b].push_back(a);
    }

    C.resize(M);
    for (int i = 0; i < M; ++i)
    {
        cin >> C[i];
        // --C[i]; not for binary tree!
    }
    seglca.init(C);

    int sq = 1;
    while (sq * sq < M)
        ++sq;
    queries.resize(Q);
    answers.resize(Q);
    for (int i = 0, l, r; i < Q; ++i)
    {
        cin >> l >> r;
        --l;
        queries[i] = {l, r, i};
    }
    sort(all(queries), [&](const query &a, const query &b)
         { if (a.l / sq != b.l / sq) return a.l < b.l; else return a.r < b.r; });

    int lx = 0, rx = 0;
    ans = 0;
    cnt.assign(N + 1, 0);
    for (query q : queries)
    {
        while (rx < q.r)
            add(C[rx++]);
        while (lx > q.l)
            add(C[--lx]);
        while (rx > q.r)
            sub(C[--rx]);
        while (lx < q.l)
            sub(C[lx++]);

        int tmp = ans;
        int lca = seglca.query(q.l, q.r);
        lca >>= 1;
        while (lca > 0)
            --tmp, lca >>= 1;

        answers[q.idx] = tmp;
    }

    for (int x : answers)
        cout << x << "\n";
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 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 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 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 212 KB Output is correct
2 Incorrect 22 ms 4524 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 932 ms 7964 KB Output is correct
5 Correct 944 ms 9348 KB Output is correct
6 Correct 1152 ms 11340 KB Output is correct
7 Correct 1229 ms 12620 KB Output is correct
8 Correct 1236 ms 12556 KB Output is correct
9 Correct 1225 ms 12552 KB Output is correct
10 Correct 1207 ms 12620 KB Output is correct
11 Correct 1271 ms 12556 KB Output is correct
12 Correct 1237 ms 12548 KB Output is correct
13 Correct 1215 ms 12664 KB Output is correct
14 Correct 161 ms 4940 KB Output is correct

Subtask #6
0 / 41.0

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