Submission #1101629

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101629		Pacybwoah	Tourism (JOI23_tourism)	C++17	100 / 100	675 ms	39368 KiB

tourism

#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){
    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){
        for(auto &x: graph[node]){
            if(x == pos) swap(graph[node][0], x);
        }
        head[pos] = node;
    }
}
void dfs_head(int node, int parent){
    ord[++cnt] = node;
    in[node] = cnt;
    if(head[node] != node) head[node] = head[parent];
    for(auto &x: graph[node]){
        if(x != parent) dfs_head(x, node);
    }
    out[node] = cnt;
}
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){
                    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: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 41 / 41