제출 #1189082

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1189082		duyngadocton	Tourism (JOI23_tourism)	C++20	0 / 100	26 ms	24844 KiB

tourism

#include<bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ii pair<int,int>
#define ll long long
#define pb push_back
#define eb emplace_back

const int MAX = (int) 2e5;
const int B = 330;

int block(int l) {
    return (l - 1) / B + 1;
}

struct queries {
    int l, r, id;

    queries(int _l = 0, int _r = 0, int _id = 0) : l(_l), r(_r), id(_id) {}
    bool operator < (queries o) {
        return ii(block(l), r) < ii(block(o.l), o.r);
    }
} query[MAX + 5];


int n, m, q;
int p[MAX + 5];
vector<int> adj[MAX + 5];
int start[MAX + 5], stop[MAX + 5], id, arr[MAX + 5];
int ans[MAX + 5];
int ds;
ii rmq[25][MAX * 2 + 5];
int id_rmq, pos[MAX + 5], lg[MAX * 2 + 5], dep[MAX + 5];
set<int> st;

void dfs(int u, int dad) {
    arr[++id] = u;
    start[u] = id;
    pos[u] = ++id_rmq;
    rmq[0][id_rmq] = ii(dep[u], u);
    for(int v : adj[u]) if(v != dad) {
        dep[v] = dep[u] + 1;
        dfs(v, u);
        rmq[0][++id_rmq] = ii(dep[u], u);
    }
    stop[u] = id;
}

int lca(int u, int v) {
    u = pos[u], v = pos[v];
    if(u > v) swap(u, v);
    int k = lg[v - u + 1];
    return min(rmq[k][u], rmq[k][v - (1 << k) + 1]).se;
}

int L(int x) {
    auto it = st.lower_bound(start[x]);
    if(it == st.begin()) return 0;
    --it;
    return arr[*it];
}

int R(int x) {
    auto it = st.lower_bound(start[x]);
    ++it;
    if(it == st.end()) return 0;
    return arr[*it];
}

int getlca() {
    auto it1 = st.begin();
    auto it2 = st.end();
    --it2;
    return lca(arr[*it1], arr[*it2]);
}

void add(int x) {
    if(st.size() == 0) {
        st.insert(start[x]);
        return ;
    }
    int w1 = getlca();
    st.insert(start[x]);
    int w2 = getlca();
    if(w1 != w2) {
        ds += dep[x] + dep[w1] - 2 * dep[w2];
    }
    else {
        int l = L(x);
        int r = R(x);
        int u = lca(l, x);
        int v = lca(r, x);
        int w = dep[u] > dep[v] ? u : v;
        ds += dep[x] - dep[w];
    }
}

void del(int x) {
    if(st.size() == 1) {
        st.erase(start[x]);
        return ;
    }
    int w1 = getlca();
    st.erase(st.find(start[x]));
    int w2 = getlca();
    if(w1 != w2) {
        ds -= dep[x] + dep[w2] - 2 * dep[w1];
    }
    else {
        int l = L(x);
        auto it = st.lower_bound(start[x]);
        int r = 0;
        if(it != st.end()) r = arr[*it];
        else r = 0;
        int u = lca(l, x);
        int v = lca(r, x);
        int w = dep[u] > dep[v] ? u : v;
        ds -= dep[x] - dep[w];
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);cout.tie(NULL);
    cin >> n >> m >> q;
    for(int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    for(int i = 1; i <= m; ++i)
        cin >> p[i];
    for(int i = 1; i <= q; ++i) {
        int l, r;
        cin >> l >> r;
        query[i] = queries(l, r, i);
    }
    sort(query + 1, query + q + 1);
    int l = 1, r = 0;
    dfs(1, 0);
    for(int i = 1; i <= id_rmq; ++i) lg[i] = log2(i);
    for(int k = 1; k <= lg[id_rmq]; ++k)
        for(int i = 1; i + (1 << k) - 1 <= id_rmq; ++i) rmq[k][i] = min(rmq[k - 1][i], rmq[k - 1][i + (1 << (k - 1))]);
    for(int i = 1; i <= q; ++i) {
        int id = query[i].id;
        while(r < query[i].r) ++r, add(p[r]);
        while(l > query[i].l) --l, add(p[l]);
        while(l < query[i].l) del(p[l]), ++l;
        while(r > query[i].r) del(p[r]), --r;
        ans[id] = ds;
    }
    for(int i = 1; i <= q; ++i) cout << ans[i] + 1 << "\n";
}

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