Submission #1183082

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183082		Gray	Tourism (JOI23_tourism)	C++20	0 / 100	5091 ms	24904 KiB

tourism

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#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> smap;

struct Tree{
    vector<vector<ll>> bin;
    vector<ll> level;
    void dfs1(ll u, ll p, ll clev, ll &timer){
        tin[u]=timer; timer++;
        level[u]=clev; bin[u][0]=p;
        for (ll i=1; i<20; i++) bin[u][i]=bin[bin[u][i-1]][i-1];
        for (auto v:A[u]){
            if (v==p) continue;
            dfs1(v, u, clev+1, timer);
        }
    }
    void init(){
        level.resize(n+1); tin.resize(n+1);
        bin.resize(n+1, vector<ll>(20));
        ll timer=0; dfs1(1, 1, 1, timer);
    }
    ll jump(ll u, ll k){
        for (ll i=0; i<20; i++){
            if (k&(1<<i)) u=bin[u][i];
        }
        return u;
    }
    ll lca(ll u, ll v){
        if (level[u]<level[v]) swap(u, v);
        u = jump(u, level[u]-level[v]);
        if (u==v) return u;
        for (ll i=19; i>=0; i--){
            if (bin[u][i]!=bin[v][i]){
                u=bin[u][i]; v=bin[v][i];
            }
        }
        return bin[u][0];
    }
    ll dist(ll u, ll v){
        ll lc = lca(u, v);
        return level[u]+level[v]-level[lc]*2;
    }
} tree;
struct TDist{
    set<pair<ll, 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], u});
            }else if (euler.size()==1){
                dist+=tree.dist(u, (*euler.begin()).ss);
                euler.insert({tin[u], u});
            }else{
                auto iter = euler.upper_bound({tin[u], u});
                if (iter==euler.end()){
                    iter--; dist-=tree.dist((*euler.begin()).ss, tree.lca((*euler.begin()).ss, (*iter).ss));
                    dist+=tree.level[u]-tree.level[tree.lca(u, (*iter).ss)];
                    dist+=tree.level[(*euler.begin()).ss]-tree.level[tree.lca(u, (*euler.begin()).ss)];
                    euler.insert({tin[u], u});
                }else if (iter==euler.begin()){
                    dist-=tree.dist((*iter).ss, tree.lca((*euler.rbegin()).ss, (*iter).ss));
                    dist+=tree.level[u]-tree.level[tree.lca(u, (*euler.rbegin()).ss)];
                    dist+=tree.level[(*iter).ss]-tree.level[tree.lca(u, (*iter).ss)];
                    euler.insert({tin[u], u});
                }else{
                    auto piter=iter; piter--;
                    dist-=tree.level[(*iter).ss]-tree.level[tree.lca((*iter).ss, (*piter).ss)];
                    dist+=tree.level[(*iter).ss]-tree.level[tree.lca((*iter).ss, u)];
                    dist+=tree.level[u]-tree.level[tree.lca(u, (*piter).ss)];
                    euler.insert({tin[u], 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((*euler.begin()).ss, (*euler.rbegin()).ss);
                euler.erase({tin[u], u});
            }else{
                auto iter = euler.find({tin[u], u});
                ll pu, nu;
                if (iter==euler.begin()){
                    iter++; pu = (*euler.rbegin()).ss; nu = (*iter).ss;
                }else if ((*iter)==(*euler.rbegin())){
                    iter--; pu = (*iter).ss; nu = (*euler.begin()).ss;
                }else{
                    iter--; pu = (*iter).ss; iter++;
                    iter++; nu = (*iter).ss;
                }
                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], 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){
                l--; add(smap[l]);
            }
            while (l<tl){
                remove(smap[l]); l++;
            }
            while (r>tr){
                remove(smap[r]); r--;
            }
            while (r<tr){
                r++; add(smap[r]);
            }
        }
    }
};

const ll B = 80;

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);
    vector<ll> res(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};
    }
    sort(sqs.begin(), sqs.end());
    TDist tdist; vector<ll> crng;
    for (ll i=0; i<=m/B; i++){
        pair<pair<ll, ll>, ll> _temp_spi = mp(mp(i, -1), -1), _temp_epi = mp(mp(i+B, -1), -1);
        ll spi = lower_bound(sqs.begin(), sqs.end(), _temp_spi)-sqs.begin();
        ll epi = lower_bound(sqs.begin(), sqs.end(), _temp_epi)-sqs.begin()-1;
        crng.clear(); for (ll j=spi; j<=epi; j++) crng.push_back(sqs[j].ss);
        sort(crng.begin(), crng.end(), [&](ll ind1, ll ind2){ return qs[ind1].ss<qs[ind2].ss; });
        for (auto j:crng){
            tdist.shift(qs[j].ff, qs[j].ss);
            res[j]=tdist.dist;
            // cout << j << ": " << tdist.dist << endl;
        }
    }
    for (ll i=0; i<q; i++){
        cout << res[i]+1 << 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: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 41