Submission #1214405

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214405		dosts	Tourism (JOI23_tourism)	C++20	28 / 100	5096 ms	43844 KiB

tourism

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int N = 1e5+1;
vi edges[N],d(N),tin(N),tout(N),anti(2*N);
int up[2*N][18];

int better(int a,int b) {
    return d[a] < d[b] ? a : b;
}

int rmq(int a,int b) {
    int ln = __lg(b-a+1);
    return better(up[a][ln],up[b-(1<<ln)+1][ln]);
}

int lca(int a,int b) {
    if (tin[a] > tin[b]) swap(a,b);
    return rmq(tin[a],tout[b]);
}

int timer = 1;
void dfs(int node,int p,int der = 0) {
    d[node] = der;
    up[timer][0] = node;
    tin[node] = tout[node] = timer++;
    anti[tin[node]] = node;
    for (auto it : edges[node]) {
        if (it == p) continue;
        dfs(it,node,der+1);
        up[timer][0] = node;
        tout[node] = timer++;
    }
}


int dst(int a,int b) {
    return d[a]+d[b]-2*d[lca(a,b)];
}

bool anc(int a,int b) {
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}

struct Query {
    int l,r,id;
};
vi ans(N);
int L,R;
int total = 0;
set<int> nds;

vi cnt(N,0);
void add(int node) {
    cnt[node]++;
    if (nds.empty()) {
        nds.insert(tin[node]);
        total++;
        return;
    }
    if (cnt[node] != 1) return;
    auto it = nds.lower_bound(tin[node]);
    if (it == nds.end()) it = nds.begin();
    auto itt = it;
    if (itt == nds.begin()) itt = prev(nds.end());
    else --itt;
    int prv = anti[*itt];
    int nxt = anti[*it];
    if (prv == nxt) {
        total = dst(prv,node)+1;
        nds.insert(tin[node]);
        return;
    }
    if (!anc(lca(prv,nxt),node)) total+=dst(lca(prv,nxt),node);
    else if (anc(prv,node) && anc(nxt,node)) total+=min(dst(prv,node),dst(nxt,node));
    else total+=min(dst(lca(prv,node),node),dst(lca(nxt,node),node));
    nds.insert(tin[node]);
}

void rem(int node) {
    cnt[node]--;
    if (cnt[node] < 0) {
        cerr << "wtf" << endl;
        exit(-1);
    }
    if (cnt[node] != 0) return;
    auto it = nds.lower_bound(tin[node]);
    auto itt = it;
    ++it;
    if (it == nds.end()) it = nds.begin();
    if (itt == nds.begin()) itt = prev(nds.end());
    else --itt;
    int prv = anti[*itt];
    int nxt = anti[*it];
    if (prv == nxt) {
        total = 1;
        nds.erase(tin[node]);
        return;
    }
    if (!anc(lca(prv,nxt),node)) total-=dst(lca(prv,nxt),node);
    else if (anc(prv,node) && anc(nxt,node)) total-=min(dst(prv,node),dst(nxt,node));
    else total-=min(dst(lca(prv,node),node),dst(lca(nxt,node),node));
    nds.erase(tin[node]);
}

vi lst(N);
void fix(int l,int r) {
    while (L > l) add(lst[--L]);
    while (R < r) add(lst[++R]);
    while (L < l) rem(lst[L++]);
    while (R > r) rem(lst[R--]);
}

void solve() {
    int n,m,q;
    cin >> n >> m >> q;
    for (int i=1;i<n;i++) {
        int a,b;
        cin >> a >> b;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    dfs(1,1);
    for (int i=1;i<18;i++) {
        for (int j = 1;j+(1<<(i-1))<timer;j++) {
            up[j][i] = better(up[j][i-1],up[j+(1<<(i-1))][i-1]);
        }
    }
    for (int i=1;i<=m;i++) cin >> lst[i];
    L = R = 1;
    add(lst[1]);
    vector<Query> qs(q+1);
    for (int i=1;i<=q;i++) {
        cin >> qs[i].l >> qs[i].r;
        qs[i].id = i;
    }
    const int B = 1000;
    sort(1+all(qs),[&](const Query& q1,const Query& q2) {
        return pii{(q1.l+B-1)/B,q1.r} < pii{(q2.l+B-1)/B,q2.r};
    });
    for (int ii=1;ii<=q;ii++) {
        fix(qs[ii].l,qs[ii].r);
        ans[qs[ii].id] = total;
    }
    for (int i=1;i<=q;i++) cout << ans[i] << '\n';
} 

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef Dodi
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

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