oj.uz

Submission #1101625

# Submission time Handle Problem Language Result Execution time Memory
1101625 2024-10-16T11:57:24 Z Pacybwoah Tourism (JOI23_tourism) C++17
31 / 100
 740 ms 36764 KB 
#include<iostream>
#include<vector>
#include<set>
#include<utility>
#include<cassert>
#include<algorithm>
using namespace std;
int n, m, q;
vector<vector<int>> graph, anc;
vector<int> vec, in, out, ord, head, sz, bit, dep;
int cnt = 0;
void dfs(int node, int parent){
    ord[++cnt] = node;
    in[node] = cnt;
    sz[node] = 1;
    anc[0][node] = parent;
    head[node] = node;
    dep[node] = dep[parent] + 1;
    int maxi = 0, pos = -1;
    for(auto &x: graph[node]){
        if(x == parent) continue;
        dfs(x, node);
        sz[node] += sz[x];
        if(maxi < sz[x]){
            maxi = sz[x];
            pos = x;
        }
    }
    if(pos > 0) head[pos] = node;
    out[node] = cnt;
}
void dfs_head(int node, int parent){
    if(head[node] != node) head[node] = head[parent];
    for(auto &x: graph[node]){
        if(x != parent) dfs_head(x, node);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> q;
    graph.resize(n + 1);
    vec.resize(m + 1);
    in.resize(n + 1);
    out.resize(n + 1);
    ord.resize(n + 1);
    head.resize(n + 1);
    sz.resize(n + 1);
    dep.resize(n + 1);
    for(int i = 1; i < n; i++){
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    anc.resize(18, vector<int>(n + 1));
    dfs(1, 1);
    dfs_head(1, 1);
    for(int i = 1; i < 18; i++) for(int j = 1; j <= n; j++) anc[i][j] = anc[i - 1][anc[i - 1][j]];
    auto lca = [&](int a, int b){
        if(dep[a] < dep[b]) swap(a, b);
        for(int i = 0; i < 18; i++){
            if((dep[a] - dep[b]) & (1 << i)) a = anc[i][a];
        }
        for(int i = 17; i >= 0; i--){
            if(anc[i][a] != anc[i][b]){
                a = anc[i][a];
                b = anc[i][b];
            }
        }
        if(a != b) return anc[0][a];
        else return a;
    };
    bit.resize(m + 1);
    for(int i = 1; i <= m; i++) cin >> vec[i];
    auto modify = [&](int pos, int val){
        while(pos <= m){
            bit[pos] += val;
            pos += (pos & -pos);
        }
    };
    auto query = [&](int pos){
        int ans = 0;
        while(pos > 0){
            ans += bit[pos];
            pos -= (pos & -pos);
        }
        return ans;
    };
    vector<vector<pair<int, int>>> sweep(m + 1);
    vector<int> ans(q);
    for(int i = 0; i < q; i++){
        int l, r;
        cin >> l >> r;
        sweep[r].emplace_back(l, i);
    }
    vector<vector<int>> st(18, vector<int>(m));
    for(int i = 1; i < m; i++) st[0][i] = lca(vec[i], vec[i + 1]);
    for(int i = 1; i < 18; i++){
        for(int j = 1; j < m; j++) st[i][j] = lca(st[i - 1][j], st[i - 1][min(m - 1, j + (1 << (i - 1)))]);
    }
    vector<int> bases(m);
    for(int i = 2; i < m; i++){
        bases[i] = bases[i - 1];
        if((1 << (bases[i] + 1)) == i) bases[i]++;
    }
    auto qlca = [&](int l, int r){
        r--;
        if(l > r) return vec[l];
        int len = r - l + 1;
        return lca(st[bases[len]][l], st[bases[len]][r - (1 << bases[len]) + 1]);
    };
    set<pair<pair<int, int>, int>> s;
    auto assign = [&](int l, int r, int col){
        assert(l <= r);
        //cout << l << " " << r << " " << col << "\n";
        while(!s.empty()){
            auto iter = s.lower_bound(make_pair(make_pair(l, 0), 0));
            if(iter == s.end()) break;
            auto [rng, scol] = (*iter);
            if(rng.first > r) break;
            s.erase(iter);
            modify(scol, -(rng.second - rng.first + 1));
            if(rng.second > r){
                modify(scol, rng.second - r);
                s.insert(make_pair(make_pair(r + 1, rng.second), scol));
            }
        }
        auto iter2 = s.lower_bound(make_pair(make_pair(l, 0), 0));
        if(iter2 != s.begin()){
            iter2 = prev(iter2);
            if((*iter2).first.second >= l){
                auto [rng2, col2] = (*iter2);
                s.erase(iter2);
                modify(col2, -(rng2.second - l + 1));
                s.insert(make_pair(make_pair(rng2.first, l - 1), col2));
                if(r < rng2.second){
                    modify(col2, rng2.second - r);
                    s.insert(make_pair(make_pair(r + 1, rng2.second), col2));
                }
            }
        }
        s.insert(make_pair(make_pair(l, r), col));
        modify(col, r - l + 1);
    };
    for(int i = 1; i <= m; i++){
        int cur = vec[i];
        while(1){
            assign(in[head[cur]], in[cur], i);
            if(head[cur] == 1) break;
            cur = anc[0][head[cur]];
        }
        for(auto &[l, id]: sweep[i]){
            ans[id] += query(i) - query(l - 1);
            ans[id] -= dep[qlca(l, i)];
        }
    }
    for(int i = 0; i < q; i++){
        cout << ans[i] + 1 << "\n";
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Incorrect 1 ms 508 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Incorrect 1 ms 508 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 3 ms 592 KB Output is correct
4 Correct 287 ms 24576 KB Output is correct
5 Correct 219 ms 26636 KB Output is correct
6 Correct 293 ms 31756 KB Output is correct
7 Correct 359 ms 36544 KB Output is correct
8 Correct 377 ms 36544 KB Output is correct
9 Correct 374 ms 36544 KB Output is correct
10 Correct 378 ms 36764 KB Output is correct
11 Correct 366 ms 36544 KB Output is correct
12 Correct 300 ms 36044 KB Output is correct
13 Correct 290 ms 36032 KB Output is correct
14 Correct 296 ms 36032 KB Output is correct
15 Correct 49 ms 25024 KB Output is correct
16 Correct 356 ms 36252 KB Output is correct
17 Correct 146 ms 13504 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Incorrect 238 ms 15024 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 336 KB Output is correct
2 Correct 1 ms 504 KB Output is correct
3 Correct 4 ms 604 KB Output is correct
4 Correct 568 ms 23540 KB Output is correct
5 Correct 564 ms 24056 KB Output is correct
6 Correct 675 ms 29692 KB Output is correct
7 Correct 740 ms 32556 KB Output is correct
8 Correct 690 ms 32580 KB Output is correct
9 Correct 672 ms 32704 KB Output is correct
10 Correct 686 ms 32652 KB Output is correct
11 Correct 655 ms 32548 KB Output is correct
12 Correct 669 ms 32704 KB Output is correct
13 Correct 665 ms 32704 KB Output is correct
14 Correct 159 ms 13504 KB Output is correct

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Incorrect 1 ms 508 KB Output isn't correct
5 Halted 0 ms 0 KB -