제출 #1019873

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1019873		Pacybwoah	Tourism (JOI23_tourism)	C++17	10 / 100	5089 ms	24472 KiB

tourism

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cassert>
#include<set>
#include<utility>
using namespace std;
const int k = 300;
vector<vector<int>> graph;
vector<int> in, dep, pos;
vector<vector<int>> anc;
int tst = 0;
void dfs(int node, int parent){
    in[++tst] = node;
    pos[node] = tst;
    anc[0][node] = parent;
    dep[node] = dep[parent] + 1;
    for(auto x: graph[node]){
        if(x == parent) continue;
        dfs(x, node);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    //assert(n <= 2000);
    in.resize(n + 1);
    dep.resize(n + 1);
    pos.resize(n + 1);
    anc.resize(18, vector<int>(n + 1));
    graph.resize(n + 1);
    int a, b;
    for(int i = 1; i < n; i++){
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    dfs(1, 1);
    vector<int> vec(m + 1);
    for(int i = 1; i <= m; i++) cin >> vec[i], vec[i] = pos[vec[i]];
    vector<int> ans(q);
    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 u, int v){
        u = in[u], v = in[v];
        if(dep[u] < dep[v]) swap(u, v);
        for(int i = 17; i >= 0; i--){
            if((1 << i) & (dep[u] - dep[v])) u = anc[i][u];
        }
        for(int i = 17; i >= 0; i--){
            if(anc[i][u] != anc[i][v]) u = anc[i][u], v = anc[i][v];
        }
        if(u != v) u = anc[0][u], v = anc[0][v];
        return pos[u];
    };
    auto dist = [&](int u, int v){
        return dep[in[u]] + dep[in[v]] - 2 * dep[in[lca(u, v)]];
    };
    auto left = [&](int aa, int bb, int cc){
        return (dist(aa, bb) + dist(aa, cc) - dist(bb, cc)) / 2;
    };
    vector<pair<pair<int, int>, int>> queries;
    for(int i = 0; i < q; i++){
        cin >> a >> b;
        queries.push_back(make_pair(make_pair(a, b), i));
    }
    auto cmp = [&](pair<pair<int, int>, int> c, pair<pair<int, int>, int> d){
        if((c.first.first - 1) / k == (d.first.first - 1) / k){
            if((c.first.first - 1) / k % 2 == 0) return c.first.second < d.first.second;
            else return c.first.second > d.first.second;
        }
        else return (c.first.first - 1) / k < (d.first.first - 1) / k;
    };
    sort(queries.begin(), queries.end(), cmp);
    int now_lca = 1;
    multiset<int> s;
    int cnt = 0;
    vector<vector<int>> st(18, vector<int>(m + 1));
    for(int i = 1; i <= m; i++) st[0][i] = vec[i];
    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, j + (1 << (i - 1)))]);
    }
    vector<int> bases(n + 1);
    int tmp = 0;
    for(int i = 1; i <= n; i++){
        if((1 << (tmp + 1)) <= i)  tmp++;
        bases[i] = tmp;
    }
    auto query = [&](int l, int r){
        tmp = r - l + 1;
        return lca(st[bases[tmp]][l], st[bases[tmp]][r - (1 << bases[tmp]) + 1]);
    };
    int lptr = 1, rptr = 0;
    auto add = [&](int node){
        if(s.empty()){
            now_lca = node;
            s.insert(node);
            cnt = 1;
            return;
        }
        auto iter = s.lower_bound(node);
        if(iter != s.end() && (*iter) == node){
            s.insert(node);
            return;
        }
        if(iter == s.begin()){
            cnt += left(node, (*iter), now_lca);
            now_lca = lca(node, now_lca);
            s.insert(node);
            return;
        }
        if(iter == s.end()){
            iter = prev(iter);
            cnt += left(node, (*iter), now_lca);
            now_lca = lca(node, now_lca);
            s.insert(node);
            return;
        }
        int bf = (*prev(iter)), gf = (*iter);
        cnt += left(node, bf, gf);
        s.insert(node);
    };
    auto sub = [&](int node){
        auto iter2 = s.lower_bound(node);
        s.erase(iter2);
        if(s.empty()) return;
        auto iter = s.lower_bound(node);
        if(iter != s.end() && (*iter) == node){
            return;
        }
        if(iter == s.begin()){
            if(n <= 2000) now_lca = query(lptr, rptr);
            cnt -= left(node, (*iter), now_lca);
            return;
        }
        if(iter == s.end()){
            iter = prev(iter);
            if(n <= 2000) now_lca = query(lptr, rptr);
            cnt -= left(node, (*iter), now_lca);
            return;
        }
        int bf = (*prev(iter)), gf = (*iter);
        cnt -= left(node, bf, gf);
    };
    for(auto &x: queries){
        a = x.first.first, b = x.first.second;
        while(a < lptr) add(vec[--lptr]);
        while(rptr < b) add(vec[++rptr]);
        while(lptr < a) lptr++, sub(vec[lptr - 1]);
        while(b < rptr) rptr--, sub(vec[rptr + 1]);
        ans[x.second] = cnt;
        //cout << now_lca;
        //cout << a << " " << b << " " << cnt << "\n";
    }
    for(int i = 0; i < q; i++) cout << ans[i] << "\n";
}
// g++ -std=c++17 pC.cpp -o run -fsanitize=undefined -fsanitize=address -Wall -Wextra -Wshadow -Wfatal-errors
/*
7 6 2
1 2
1 3
2 4
2 5
3 6
3 7
2 3 6 4 5 7
1 3
4 6
*/

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 41