Submission #944907

#	Time	Username	Problem	Language	Result	Execution time	Memory
944907		phoenix0423	Tourism (JOI23_tourism)	C++17	10 / 100	5063 ms	61408 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")
#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 = 3e5 + 5;
const int INF = 1e9 + 7;
int n, m, q;
vector<int> adj[maxn];
int dep[maxn], in[maxn], dfn = 0;
int arr[maxn][18];
int id[maxn];

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

int lca(int a, int b){
    if(a > b) swap(a, b);
    int len = __lg(b - a + 1);
    return min(arr[a][len], arr[b - (1 << len) + 1][len]);
}

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;
    };
};
vector<info> b[500];
const int block = 320;
int ans[maxn];
int c[maxn], loc[maxn];
int cur = 0;
int path(int a, int b){
    return dep[a] + dep[b] - 2 * lca(in[a], in[b]);
}
struct node{
    int l, r, val;
} st[maxn];

struct rollback{
    int l, r, m;
};
stack<rollback> stk;
void roll_back(){
    auto [l, r, m] = stk.top(); stk.pop();
    cur -= path(st[l].val, st[r].val);
    cur += path(st[l].val, st[m].val) + path(st[m].val, st[r].val);
    st[l].r = m, st[r].l = m;
}
void del(int x){
    x = loc[x];
    int prv = st[x].l, nxt = st[x].r;
    stk.push({prv, nxt, x});
    cur -= path(st[prv].val, st[x].val) + path(st[x].val, st[nxt].val);
    cur += path(st[prv].val, st[nxt].val);
    st[prv].r = nxt, st[nxt].l = prv;
}

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 = 1; (1 << i) <= dfn; i++){
        for(int j = 0; j + (1 << i) - 1 <= dfn; j++){
            arr[j][i] = min(arr[j][i - 1], arr[j + (1 << (i - 1))][i - 1]);
        }
    }
    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++){
        sort(b[i].begin(), b[i].end());
    }
    vector<pll> cpy;
    for(int i = 0; i < m; i++) cpy.eb(c[i], i);
    sort(cpy.begin(), cpy.end(), [&](pll a, pll b){ return in[a.f] < in[b.f];});
    for(int i = 0; i < m; i++){
        auto [val, id] = cpy[i];
        loc[id] = i;
        st[i].val = val;
        if(!i) st[i].l = m - 1;
        else st[i].l = i - 1;
        if(i == m - 1) st[i].r = 0;
        else st[i].r = i + 1;
    }
    for(int i = 0; i < m; i++) cur += path(st[i].val, st[st[i].r].val);
    int cl = 0, cr = m - 1;
    for(int i = 0; i <= m / block; i++){
        if(!b[i].size()) continue;
        for(auto [l, r, id] : b[i]){
            while(r > cr){
                roll_back();
                cr++;
            }
            while(r < cr){
                del(cr--);
            }
            while(cl < l) del(cl++);
            ans[id] = cur;
            while(cl > 0){
                roll_back();
                cl--;
            }
        }
    }
    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: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 41