Submission #944827

#	Time	Username	Problem	Language	Result	Execution time	Memory
944827		phoenix0423	Tourism (JOI23_tourism)	C++17	28 / 100	5063 ms	38480 KiB

tourism

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0);
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long
#define lowbit(x) x&-x
const int maxn = 2e5 + 5;
const int INF = 1e9 + 7;
int n, m, q;
vector<int> adj[maxn];
int dep[maxn], in[maxn], dfn = 0;
int succ[maxn][18];
int id[maxn];

void dfs(int pos, int prev){
    succ[pos][0] = prev;
    for(int i = 1; i < 18; i++) succ[pos][i] = succ[succ[pos][i - 1]][i - 1];
    in[pos] = ++dfn;
    id[dfn] = pos;
    for(auto x : adj[pos]){
        if(x == prev) continue;
        dep[x] = dep[pos] + 1;
        dfs(x, pos);
    }
}

void lift(int &b, int steps){
    for(int i = 17; i >= 0; i--){
        if(steps & (1 << i)) b = succ[b][i];
    }
}

int lca(int a, int b){
    if(dep[a] > dep[b]) swap(a, b);
    lift(b, dep[b] - dep[a]);
    if(a == b) return a;
    for(int i = 17; i >= 0; i--){
        if(succ[a][i] != succ[b][i]) a = succ[a][i], b = succ[b][i];
    }
    return succ[a][0];
}


struct info{
    int l, r, id;
    info(){}
    info(int _l, int _r, int _id) : l(_l), r(_r), id(_id){}
    bool operator < (const info& other) const{
        return r < other.r;
    };
    bool operator > (const info& other) const{
        return r > other.r;
    }
};
vector<info> b[500];
const int block = 320;
int ans[maxn];
int c[maxn];
int cur = 0;
multiset<int> st;
int path(int a, int b){
    a = id[a], b = id[b];
    return dep[a] + dep[b] - 2 * dep[lca(a, b)];
}
void add(int x){
    x = in[c[x]];
    st.insert(x);
    if(st.size() == 1) return;
    auto it = st.lower_bound(x);
    auto itp = (it == st.begin() ? prev(st.end()) : prev(it));
    auto itn = (it == prev(st.end()) ? st.begin() : next(it));
    cur -= path(*itp, *itn);
    cur += path(*it, *itp);
    cur += path(*it, *itn);
}
void del(int x){
    x = in[c[x]];
    auto it = st.lower_bound(x);
    auto itp = (it == st.begin() ? prev(st.end()) : prev(it));
    auto itn = (it == prev(st.end()) ? st.begin() : next(it));
    cur += path(*itp, *itn);
    cur -= path(*it, *itp);
    cur -= path(*it, *itn);
    st.erase(it);
}

signed main(void){
    fastio;
    cin>>n>>m>>q;
    for(int i = 0; i < n - 1; i++){
        int a, b;
        cin>>a>>b;
        a--, b--;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    dfs(0, 0);
    for(int i = 0; i < m; i++) cin>>c[i], c[i] --;
    for(int i = 0; i < q; i++){
        int l, r;
        cin>>l>>r;
        l--, r--;
        b[l / block].pb(info(l, r, i));
    }
    for(int i = 0; i < m / block; i++){
        if(i % 2) sort(b[i].begin(), b[i].end(), greater<info>());
        else sort(b[i].begin(), b[i].end());
    }
    int cl = 0, cr = -1;
    for(int i = 0; i <= m / block; i++){
        for(auto [l, r, id] : b[i]){
            while(cr < r) add(++cr);
            while(cl > l) add(--cl);
            while(cr > r) del(cr--);
            while(cl < l) del(cl++);
            ans[id] = cur;
        }
    }
    for(int i = 0; i < q; i++) cout<<ans[i] / 2 + 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