Submission #1303088

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303088		zNatsumi	Tourism (JOI23_tourism)	C++20	28 / 100	5094 ms	51276 KiB

tourism

#include <bits/stdc++.h>

using namespace std;

using ii = pair<int, int>;

const int N = 1e5 + 5;
const int T = 300;

int n, m, q, a[N], in[N], arr[N<<1], it, depth[N], lg[N<<1], answer[N];
ii mn[N<<1][25];
vector<int> ad[N];
vector<array<int, 3>> Que;

void dfs(int u, int p){
    in[u] = ++it;
    arr[it] = u;
    mn[it][0] = {depth[u], u};

    for(auto v : ad[u]) if(v != p){
        depth[v] = depth[u] + 1;
        dfs(v, u);
        mn[++it][0] = {depth[u], u};
    }
}

inline void init(){
    for(int j = 1; j <= 17; ++j)
        for(int i = 1; i + (1 << j) - 1 <= it; ++i){
            mn[i][j] = min(mn[i][j - 1], mn[i + (1 << j - 1)][j - 1]);
        }

    for(int i = 2; i <= it; ++i) lg[i] = lg[i>>1] + 1;
}

inline int lca(int u, int v){
    int l = in[u], r = in[v];
    if(l > r) swap(l, r);
    int k = lg[r - l + 1];
    return min(mn[l][k], mn[r - (1 << k) + 1][k]).second;
}

inline int dist(int u, int v){
    return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}

int counter[N], total;
set<int> s;

void add(int u){
    counter[u] += 1;
    if(counter[u] > 1) return;

    s.insert(in[u]);

    auto it = s.find(in[u]);

    auto R = (next(it) != s.end() ? next(it) : s.begin());
    auto L = (it != s.begin() ? prev(it) : prev(s.end()));

    total += dist(arr[*L], u) + dist(u, arr[*R]) - dist(arr[*L], arr[*R]);
}

void del(int u){
    counter[u] -= 1;
    if(counter[u] > 0) return;

    auto it = s.find(in[u]);

    auto R = (next(it) != s.end() ? next(it) : s.begin());
    auto L = (it != s.begin() ? prev(it) : prev(s.end()));

    total += dist(arr[*L], arr[*R]) - dist(arr[*L], u) - dist(u, arr[*R]);

    s.erase(in[u]);
}

int32_t main(){
    cin.tie(0)->sync_with_stdio(0);

//    #define task "test"
//    if(fopen(task ".inp", "r")){
//        freopen(task ".inp", "r", stdin);
//        freopen(task ".out", "w", stdout);
//    }

    cin >> n >> m >> q;
    for(int i = 2; i <= n; ++i){
        int u, v; cin >> u >> v;
        ad[u].push_back(v);
        ad[v].push_back(u);
    }
    for(int i = 1; i <= m; ++i) cin >> a[i];

    dfs(1, -1);
    init();

    for(int i = 1; i <= q; ++i){
        int l, r; cin >> l >> r;
        Que.push_back({l, r, i});
    }

    sort(Que.begin(), Que.end(), [&](array<int, 3> x, array<int, 3> y){
                return make_pair(x[0] / T, x[1]) < make_pair(y[0] / T, y[1]);
         });

    int tl = 1, tr = 0;
    for(auto [l, r, idx] : Que){
        while(tr < r) add(a[++tr]);
        while(tl > l) add(a[--tl]);
        while(tr > r) del(a[tr--]);
        while(tl < l) del(a[tl++]);

        answer[idx] = total/ 2 + 1;
    }

    for(int i = 1; i <= q; ++i) cout << answer[i] << "\n";

    return 0;
}

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