oj.uz

Submission #1101613

# Submission time Handle Problem Language Result Execution time Memory
1101613 2024-10-16T11:45:08 Z Pacybwoah Tourism (JOI23_tourism) C++17
31 / 100
 703 ms 36636 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){
        //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){
                    assert(0);
                    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 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Runtime error 2 ms 592 KB Execution killed with signal 6
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 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Runtime error 2 ms 592 KB Execution killed with signal 6
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 504 KB Output is correct
3 Correct 3 ms 592 KB Output is correct
4 Correct 292 ms 24660 KB Output is correct
5 Correct 217 ms 26640 KB Output is correct
6 Correct 277 ms 31536 KB Output is correct
7 Correct 366 ms 36540 KB Output is correct
8 Correct 373 ms 36520 KB Output is correct
9 Correct 365 ms 36544 KB Output is correct
10 Correct 363 ms 36544 KB Output is correct
11 Correct 345 ms 36636 KB Output is correct
12 Correct 283 ms 36032 KB Output is correct
13 Correct 267 ms 36032 KB Output is correct
14 Correct 279 ms 36032 KB Output is correct
15 Correct 49 ms 25024 KB Output is correct
16 Correct 340 ms 36252 KB Output is correct
17 Correct 140 ms 13512 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Runtime error 142 ms 29124 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 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 540 ms 23528 KB Output is correct
5 Correct 552 ms 24060 KB Output is correct
6 Correct 647 ms 29840 KB Output is correct
7 Correct 703 ms 32544 KB Output is correct
8 Correct 659 ms 32704 KB Output is correct
9 Correct 656 ms 32564 KB Output is correct
10 Correct 648 ms 32648 KB Output is correct
11 Correct 657 ms 32640 KB Output is correct
12 Correct 656 ms 32688 KB Output is correct
13 Correct 650 ms 32704 KB Output is correct
14 Correct 164 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 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Runtime error 2 ms 592 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -