제출 #1306472

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306472		Hamed_Ghaffari	Tourism (JOI23_tourism)	C++20	100 / 100	273 ms	27956 KiB

tourism

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

#define X first
#define Y second

const int MXN = 1e5+5;

int m, fen[MXN];
inline void updx(int p, int x) {
    for(++p; p<=m+1; p+=p&-p) fen[p] += x;
}
inline int getx(int p) {
    int res=0;
    for(++p; p; p-=p&-p) res += fen[p];
    return res;
}

int n, sz[MXN], par[MXN];
vector<int> g[MXN];

void dfs(int v) {
    sz[v] = 1;
    for(int u : g[v]) if(u!=par[v])
        par[u] = v,
        dfs(u),
        sz[v] += sz[u];
}

int stt[MXN], timer, hd[MXN];
set<pii> st[MXN];

void dfs2(int v) {
    stt[v] = timer++;
    if(!hd[v]) {
        hd[v] = v;
        st[v].insert({stt[v], 0});
    }
    int big = 0;
    for(int u : g[v])
        if(u!=par[v] && (!big || sz[u]>sz[big]))
            big = u;
    if(!big) {
        st[hd[v]].insert({stt[v]+1, 0});
        return;
    }
    hd[big] = hd[v];
    dfs2(big);
    for(int u : g[v])
        if(u!=par[v] && u!=big)
            dfs2(u);
}
inline void upd_chain(int i, int l, int r, int x) {
    auto it = st[i].lower_bound(pii(l, 0));
    if(it->X>l) {
        if(it->X>r+1) {
            updx(prev(it)->Y, -(r-l+1));
            updx(x, r-l+1);
            st[i].insert({r+1, prev(it)->Y});
            st[i].insert({l, x});
            return;
        }
        updx(prev(it)->Y, l-it->X);
    }
    while(it->X<=r) {
        pii pp = *it;
        it = st[i].erase(it);
        if(it->X>r+1) {
            updx(pp.Y, pp.X-(r+1));
            st[i].insert(pii(r+1, pp.Y));
            break;
        }
        updx(pp.Y, pp.X-it->X);
    }
    updx(x, r-l+1);
    st[i].insert({l, x});
}
inline void upd(int u, int v, int x) {
    while(hd[u]!=hd[v]) {
        if(stt[u]<stt[v]) swap(u, v);
        upd_chain(hd[u], stt[hd[u]], stt[u], x);
        u = par[hd[u]];
    }
    upd_chain(hd[u], min(stt[u], stt[v]), max(stt[u], stt[v]), x);
}

int q, c[MXN], ans[MXN];
vector<pii> Q[MXN];

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> m >> q;
    for(int i=1,u,v; i<n; i++) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1);
    dfs2(1);
    updx(0, n);
    for(int i=1; i<=m; i++) cin >> c[i];
    for(int i=1, l,r; i<=q; i++) {
        cin >> l >> r;
        if(l==r) ans[i] = 1;
        else Q[r].push_back({l, i});
    }
    for(int i=1; i<=m; i++) {
        if(i>1) upd(c[i], c[i-1], i-1);
        for(auto [l, id] : Q[i])
            ans[id] = n-getx(l-1);
    }
    for(int i=1; i<=q; i++)
        cout << ans[i] << '\n';
    return 0;
}

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