Submission #1200982

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200982		nathan4690	Tourism (JOI23_tourism)	C++20	100 / 100	130 ms	40844 KiB

tourism

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define f1(i,n) for(int i=1;i<=n;i++)
#define __file_name ""
using namespace std;
const ll maxn=1e5+5, inf=1e18;

template<class T>
struct FenwickTree{
    int n;
    vector<T> bit;
    FenwickTree(){}
    FenwickTree(int n): n(n), bit(n+1, 0){}
    void update(int idx, T v){
        if(idx <= 0) return;
        for(;idx<=n;idx+=(idx&-idx)) bit[idx]+=v;
    }
    T getSum(int idx){
        if(idx <= 0) return 0;
        T res = 0;
        for(;idx;idx-=idx&-idx) res += bit[idx];
        return res;
    }
};

#define BITL FenwickTree<long long>

struct Query{
    int l, r, idx;
    bool operator<(const Query &rhs) const{
        return r < rhs.r;
    }
};

int n, m, q, c[maxn], dep[maxn], sz[maxn], par[17][maxn], ans[maxn];
pair<int,int> ST[17][maxn];
vector<int> G[maxn];
Query qu[maxn];
FenwickTree<int> fen;

int sp[maxn], revsp[maxn], timer = 1;
void preproc(int u, int p){
    revsp[timer] = u;
    sp[u] = timer++;
    par[0][u] = p;
    f1(i, 16) par[i][u] = par[i-1][par[i-1][u]];
    sz[u] = 1;
    for(int c: G[u]){
        if(c != p){
            dep[c] = dep[u] + 1;
            preproc(c, u);
            sz[u] += sz[c];
        }
    }
}

int LCA(int u, int v){
    if(dep[u] > dep[v]) swap(u, v);
    int l = dep[v] - dep[u];
    for(int i=0;i<17;i++) {
        if(l >> i & 1) v = par[i][v];
    }
    if(u == v) return u;
    for(int i=16;i>=0;i--){
        if(par[i][u] != par[i][v]){
            u = par[i][u];
            v = par[i][v];
        }
    }
    return par[0][u];
}

int head[maxn], id[maxn], cchain = 1;
// {node, last_updated}
vector<pair<int,int>> upd[maxn];

void hld(int u, int p){
    id[u] = cchain;
    int mx_sz = 0, mx_child = 0;
    for(int c: G[u]){
        if(c != p){
            if(sz[c] > mx_sz){
                mx_sz = sz[c];
                mx_child = c;
            }
        }
    }
    if(mx_child) {
        hld(mx_child, u);
    }
    for(int c: G[u]){
        if(c != p && c != mx_child){
            cchain++;
            head[cchain] = c;
            hld(c, u);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if(fopen(__file_name ".inp", "r")){
        freopen(__file_name ".inp", "r", stdin);
        freopen(__file_name ".out", "w", stdout);
    }
    // code here
    cin >> n >> m >> q;
    f1(i,n-1){
        int u, v; cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dep[1] = 1;
    preproc(1, 0);
    head[1] = 1;
    hld(1, 0);
    f1(i,m) {
        cin >> c[i];
        ST[0][i] = {sp[c[i]], sp[c[i]]};
    }
    f1(b, 16){
        f1(i,m) {
            ST[b][i] = {min(ST[b-1][i].first, ST[b-1][i + (1 << (b-1))].first),
                        max(ST[b-1][i].second, ST[b-1][i + (1 << (b-1))].second)};
        }
    }
    f1(i, q){
        int l, r; cin >> l >> r;
        qu[i] = {l, r, i};
    }
    sort(qu+1,qu+q+1);
    fen = FenwickTree<int>(m);
    int ptr = 1;
    f1(i,m){
        int u = c[i];
        while(u != 0){
            int p = par[0][head[id[u]]];
            int la = p;
            while(!upd[id[u]].empty()){
                int v = upd[id[u]].back().first, pos = upd[id[u]].back().second;
                if(dep[v] <= dep[u]){
                    fen.update(pos, -(dep[v] - dep[la]));
                    la = v;
                    upd[id[u]].pop_back();
                }else{
                    fen.update(pos, -(dep[u] - dep[la]));
                    break;
                }
            }
            upd[id[u]].push_back({u, i});
            fen.update(i, dep[u] - dep[p]);
            u = p;
        }
        while(ptr <= q && qu[ptr].r == i){
            int l = qu[ptr].l, r = qu[ptr].r;
            int b = __lg(r - l + 1);
            int x = min(ST[b][l].first, ST[b][r - (1 << b) + 1].first);
            int y = max(ST[b][l].second, ST[b][r - (1 << b) + 1].second);
            x = revsp[x]; y = revsp[y];
            ans[qu[ptr].idx] = fen.getSum(qu[ptr].r) - fen.getSum(qu[ptr].l - 1) - dep[LCA(x, y)] + 1;
            ptr++;
        }
    }
    f1(i,q) cout << ans[i] << '\n';
    return 0;
}

Compilation message (stderr)

tourism.cpp: In function 'int main()':
tourism.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         freopen(__file_name ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         freopen(__file_name ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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