Submission #1189077

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189077		duyngadocton	Tourism (JOI23_tourism)	C++20	28 / 100	5094 ms	41216 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) 1e5;
const int B = 320;

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];
multiset<int> st;

//struct segtree {
//    void update(int id, int l, int r, int p, int x) {
//        if(l > p || r < p) return;
//        if(l == r) {
//            st[id] = x;
//            return ;
//        }
//        int mid = l + r >> 1;
//        update(id * 2, l, mid, p, x);
//        update(id * 2 + 1, mid + 1, r, p, x);
//        st[id] = st[id * 2] + st[id * 2 + 1];
//    }
//
//    int get(int id, int l, int r, int u, int v) {
//        if(l > v || r < u) return 0;
//        if(u <= l && r <= v) return st[id];
//        int mid = l + r >> 1;
//        return get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v);
//    }
//} st_start, st_stop, st_child;

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) {
//        if(x == 3) cout << x << " " << ds << " " << x << " " << " 1234\n";
        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) cout << query[i].l << " " << query[i].r << " " << query[i].id << '\n';
    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;
//        if(ds == 6) cout << id << " 12345\n";
        while(r > query[i].r) del(p[r]), --r;
        ans[id] = ds;
//        if(id == 1) cout << ds << ' ' << l << " " << r << '\n';
    }
    for(int i = 1; i <= q; ++i) cout << ans[i] + 1 << "\n";
}

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