Submission #1183907

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183907		Gray	Tourism (JOI23_tourism)	C++20	28 / 100	5094 ms	65556 KiB

tourism

#include <bits/stdc++.h>
using namespace std;
#define ll int
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair
#define pb push_back
#define INF (ll)2e18
#define MOD (ll)(1e9+7)

ll n, m, q;
vector<vector<ll>> A;
vector<ll> tin;
vector<ll> btin;
vector<ll> smap;
struct Tree{
    vector<vector<pair<ll, ll>>> st;
    vector<ll> level, eid, log;
    vector<pair<ll, ll>> euler;
    void dfs1(ll u, ll p, ll clev, ll &timer){
        tin[u]=timer; timer++; level[u]=clev; btin[timer-1]=u;
        euler.push_back({clev, u}); eid[u]=euler.size()-1;
        for (auto v:A[u]){
            if (v==p) continue;
            dfs1(v, u, clev+1, timer);
            euler.push_back({clev, u});
        }
    }

    void genST(){
        ll N = euler.size(); log.resize(N+1);
        for (ll i=2; i<=N; i++) log[i]=log[i/2]+1;
        st.resize(log[N]+1, vector<pair<ll, ll>>(N));
        st[0] = euler;
        for (ll i=1; i<=log[N]; i++){
            for (ll j=0; j<=N-(1<<i); j++){
                st[i][j]=min(st[i-1][j], st[i-1][j+(1<<(i-1))]);
            }
        }
    }
    void init(){
        level.resize(n+1); tin.resize(n+1);
        eid.resize(n+1); btin.resize(n);
        euler.resize(n+1); ll timer=0;
        dfs1(1, 1, 1, timer); genST();
    }

    ll lca(ll u, ll v){
        ll l = eid[u], r = eid[v];
        if (l>r) swap(l, r);
        ll lg = log[r-l+1];
        return min(st[lg][l], st[lg][r-(1<<lg)+1]).ss;
    }

    ll dist(ll u, ll v){
        ll lc = lca(u, v);
        return level[u]+level[v]-level[lc]*2;
    }
} tree;

ll pcnt=0;

struct TDist{
    set<ll> euler;
    vector<ll> cnt; ll dist, l, r;
    TDist(){
        cnt.resize(n+1); dist=0;
        l=-1; r=-1;
    }
    void add(ll u){
        // cout << "added " << u << " -> ";
        cnt[u]++; if (cnt[u]==1){
            if (euler.empty()){
                euler.insert(tin[u]);
            }else if (euler.size()==1){
                dist+=tree.dist(u, btin[(*euler.begin())]);
                euler.insert(tin[u]);
            }else{
                auto iter = euler.upper_bound(tin[u]);
                if (iter==euler.end()){
                    iter--; dist-=tree.dist(btin[(*euler.begin())], tree.lca(btin[(*euler.begin())], btin[(*iter)]));
                    dist+=tree.level[u]-tree.level[tree.lca(u, btin[(*iter)])];
                    dist+=tree.level[btin[(*euler.begin())]]-tree.level[tree.lca(u, btin[(*euler.begin())])];
                }else if (iter==euler.begin()){
                    dist-=tree.dist(btin[(*iter)], tree.lca(btin[(*euler.rbegin())], btin[(*iter)]));
                    dist+=tree.level[u]-tree.level[tree.lca(u, btin[(*euler.rbegin())])];
                    dist+=tree.level[btin[(*iter)]]-tree.level[tree.lca(u, btin[(*iter)])];
                }else{
                    auto piter=iter; piter--;
                    dist-=tree.level[btin[(*iter)]]-tree.level[tree.lca(btin[(*iter)], btin[(*piter)])];
                    dist+=tree.level[btin[(*iter)]]-tree.level[tree.lca(btin[(*iter)], u)];
                    dist+=tree.level[u]-tree.level[tree.lca(u, btin[(*piter)])];
                }
                euler.insert(tin[u]);
            }
        }
        // cout << dist << ln;
    }
    void remove(ll u){
        // cout << "removed " << u << " -> ";
        cnt[u]--; if (cnt[u]==0){
            if (euler.size()==1){
                euler.erase(euler.begin());
            }else if (euler.size()==2){
                dist-=tree.dist(btin[*euler.begin()], btin[*euler.rbegin()]);
                euler.erase(tin[u]);
            }else{
                auto iter = euler.find(tin[u]);
                ll pu, nu;
                if (iter==euler.begin()){
                    iter++; pu = btin[(*euler.rbegin())]; nu = btin[(*iter)];
                }else if ((*iter)==(*euler.rbegin())){
                    iter--; pu = btin[(*iter)]; nu = btin[(*euler.begin())];
                }else{
                    iter--; pu = btin[(*iter)]; iter++;
                    iter++; nu = btin[(*iter)];
                }
                dist-=tree.level[u]-tree.level[tree.lca(pu, u)];
                dist-=tree.level[nu]-tree.level[tree.lca(u, nu)];
                dist+=tree.level[nu]-tree.level[tree.lca(pu, nu)];
                euler.erase(tin[u]);
            }
        }
        // cout << dist << ln;
    }
    void shift(ll tl, ll tr){
        if (l==-1 and r==-1){
            l=tl; r=tr;
            for (ll i=l; i<=r; i++) add(smap[i]);
        }else{
            while (l>tl){
                pcnt++;
                l--; add(smap[l]);
            }
            while (r<tr){
                pcnt++;
                r++; add(smap[r]);
            }
            while (l<tl){
                pcnt++;
                remove(smap[l]); l++;
            }
            while (r>tr){
                pcnt++;
                remove(smap[r]); r--;
            }
        }
    }
};





ll B = 780;

void solve(){
    cin >> n >> m >> q; A.resize(n+1);
    for (ll i=0; i<n-1; i++){
        ll u, v; cin >> u >> v;
        A[u].push_back(v); A[v].push_back(u);
    }
    tree.init();
    smap.resize(m);
    for (ll i=0; i<m; i++) cin >> smap[i];
    vector<pair<ll, ll>> qs(q);
    vector<pair<pair<ll, ll>, ll>> sqs(q);
    for (ll i=0; i<q; i++){
        cin >> qs[i].ff >> qs[i].ss; qs[i].ff--; qs[i].ss--;
        sqs[i] = {qs[i], i};
    }
    TDist tdist; vector<ll> crng;
    vector<ll> res(q);
    stable_sort(sqs.begin(), sqs.end(), [&](auto op1, auto op2){
        if (op1.ff.ff/B==op2.ff.ff/B) return op1.ff.ss<op2.ff.ss;
        return op1.ff.ff/B<op2.ff.ff/B;
    });
    for (auto &[rng, i]:sqs){
        tdist.shift(rng.ff, rng.ss); res[i] = tdist.dist;
    }
    for (ll i=0; i<q; i++){
        cout << res[i]+1 << ln;
    }
    // cout << n << " - " << m << " - " << q << " - " << pcnt << ln;
    // cout << pcnt/n << ln;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    #ifdef LOCAL
    auto start = chrono::high_resolution_clock::now();
    #endif
    ll t=1;
    // cin >> t;
    for (ll c=1; c<=t; c++) solve();
    #ifdef LOCAL
    auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
    cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
    #endif
}

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