Submission #1261792

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261792		niepamietamhasla	Tourism (JOI23_tourism)	C++20	100 / 100	1367 ms	48404 KiB

tourism

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int,int>
#define vii vector<pair<int,int>>
#define vi vector<int>

const int MAXN = 1e5 + 5;

struct d{
    int a;
    int b;
    int dist;
};

int n, m, q;
int miejsca[MAXN];

vector<pii> graf[MAXN];
int odlodroota[MAXN];
int gl[MAXN];
int pre[MAXN];
int post[MAXN];
int przodek[MAXN][17];
int wartoscpre[MAXN];

vector<d> szuk;
int cnt = 0;
int it = 0;
set<int> tmp;
vector<int> uzyteczne;

void dfs(int v, int p){
    pre[v] = cnt;
    wartoscpre[cnt] = v;
    //cout << v << " " << pre[v] << " pre\n";
    post[v] = cnt;
    cnt++;
    for(auto u : graf[v]){
        if(u.first == p) continue;
        gl[u.first] = gl[v] + 1;
        przodek[u.first][0] = v;
        odlodroota[u.first] = odlodroota[v] + u.second;
        for(int j = 1; j < 17; ++j){
            przodek[u.first][j] = przodek[przodek[u.first][j-1]][j-1];
        }
        dfs(u.first, v);
        post[v] = post[u.first];
    }
    return;
}

int obliczLCA(int x, int y){
    if(x == y) return x;
    if(gl[x] < gl[y]) swap(x, y);
    for(int i = 16; i >= 0; --i){
        if(gl[x] - (1 << i) >= gl[y]){
            x = przodek[x][i];
        }
    }
    if(x == y) return x;
    for(int i = 16; i >= 0; --i){
        if(gl[x] >= (1 << i) and przodek[x][i] != przodek[y][i]){
            x = przodek[x][i];
            y = przodek[y][i];
        }
    }
    return przodek[x][0];
}

void dfs2(int v, int p){
    bool c = (it != uzyteczne.size() and wartoscpre[uzyteczne[it]] == v);
    if(c) ++it;
    int last = -1;
    for(auto u : graf[v]){
        if(u.first == p) continue;
        if(c and it != last and it != uzyteczne.size() and uzyteczne[it] >= pre[v] and uzyteczne[it] <= post[v]){
            //cout << v << " " << wartoscpre[uzyteczne[it]] << " nowa kraw do grafu\n";
            szuk.push_back({v, wartoscpre[uzyteczne[it]], odlodroota[wartoscpre[uzyteczne[it]]] - odlodroota[v]});
            last = it;
        }
        dfs2(u.first, v);
    }
    return;
}   

void generujkrawedzie(const vector<d> &starekrawedzie, int nowyroot, int poczatekmiejsc, int koniecmiejsc){
    if(poczatekmiejsc >= koniecmiejsc) {
        szuk.clear();
        return;
    }
    cnt = 0;
    it = 0;
    szuk.clear();
    uzyteczne.clear();
    tmp.clear();
    for(auto u : starekrawedzie){
        graf[u.a].push_back({u.b, u.dist});
        graf[u.b].push_back({u.a, u.dist});
    }
    dfs(nowyroot, -1);
    //cout << poczatekmiejsc << " " << koniecmiejsc << " pk\n";
    for(int i = poczatekmiejsc; i <= koniecmiejsc; ++i){
        if(pre[miejsca[i]] != 0) {
            uzyteczne.push_back(pre[miejsca[i]]);
        }
    }
    sort(uzyteczne.begin(),uzyteczne.end());
    for(int i = 0; i < (int)uzyteczne.size()-1; ++i){
        int x = wartoscpre[uzyteczne[i]];
        int y = wartoscpre[uzyteczne[i+1]];
        //cout << x << " " << y << " gen LCA\n";
        int LCA = obliczLCA(x, y);
        //cout << LCA << " LCA\n";
        tmp.insert(pre[LCA]);
    }
    for(auto u : uzyteczne){
        tmp.insert(u);
    }
    tmp.insert(0);
    uzyteczne.clear();
    for(auto u : tmp){
        uzyteczne.push_back(u);
    }
    dfs2(nowyroot, -1);
    for(auto u : starekrawedzie){
        for(auto t : {u.a, u.b}){
            graf[t].clear();
            pre[t] = 0;
            post[t] = 0;
            odlodroota[t] = 0;
            for(int i = 0; i < 17; ++i){
                przodek[t][i] = 0;
            }
            gl[t] = 0;
        }
    }
    for(int i = 0; i < cnt; ++i){
        wartoscpre[i] = 0;
    }
    // for(auto u : szuk){
    //     cout << u.a << " " << u.b << " " << u.dist << " U\n";
    // }
    return;
}

struct e{
    int l;
    int r;
    int org;
};



int ans[MAXN];
pii przedzialy[MAXN];

struct f{
    int l;
    int r;
    int typ;
    int last;
};

vector<f> sweep;

const int base = 1 << 17;
int drzew[base << 1];

void akt(int w, int val){
    w += base;
    while(w != 0){
        drzew[w] += val;
        w /= 2;
    }
    return;
}

int obl(int w, int a, int b, int akt_a, int akt_b){
    if(a <= akt_a and akt_b <= b) return drzew[w];
    if(akt_a > b or akt_b < a) return 0;
    int mid = (akt_a + akt_b) / 2;
    return obl(2 * w, a, b, akt_a, mid) + obl(2 * w + 1, a, b, mid + 1, akt_b);
}

set<int> ind[MAXN];

void dfs3(int v, int p, int mid, int koszt){
    //cout << v << " " << p << " vp\n";
    if(ind[v].size() == 0) przedzialy[v] = {0, m + 1};
    else{
        auto it = ind[v].upper_bound(mid);
        if(it == ind[v].begin()) przedzialy[v].first = 0;
        else przedzialy[v].first = *(--it);
        it = ind[v].upper_bound(mid);
        if(it == ind[v].end()){
            przedzialy[v].second = m+1;
        } 
        else przedzialy[v].second = *it;
    }
    for(auto u : graf[v]){
        if(u.first == p) continue;
        dfs3(u.first, v, mid, u.second);
        przedzialy[v].first = max(przedzialy[v].first, przedzialy[u.first].first);
        przedzialy[v].second = min(przedzialy[v].second, przedzialy[u.first].second);
    }
    if(v != miejsca[mid]){
        //cout << v << " " << przedzialy[v].first << " " << przedzialy[v].second << " przedzial\n";
        //cout << przedzialy[v].first << " " << koszt << " ADDDDD\n";
        akt(przedzialy[v].first, koszt);
        sweep.push_back({przedzialy[v].first, przedzialy[v].second, 0, koszt});
    }
    return;
}

bool comp(const f &f1, const f &f2){
    if(f1.r != f2.r) return f1.r < f2.r;
    if(f1.typ != f2.typ) return f1.typ < f2.typ;
    return false;
}

void daq(const vector<d> &kraw, int root, int l, int r, vector<e> &queries){
    if(l > r){
        //cout << l << " " << r << " zly\n";
        return;
    }
    if(l == r){
        //cout << l << " " << r << " rowny\n";
        for(auto u : queries){
            ans[u.org] = 1;
        }
        return;
    }
    // cout << root << " " << l << " " << r << " lr\n";
    // for(auto u : kraw){
    //     cout << u.a << " " << u.b << " " << u.dist << " graf\n";
    // }
    for(int i = l; i <= r; ++i){
        ind[miejsca[i]].insert(i);
    }

    vector<e> lewe;
    vector<e> prawe;
    vector<e> reszta;
    int split = (l + r) / 2;
    for(auto u : queries){
        if(u.r < split) lewe.push_back(u);
        else if(u.l > split) prawe.push_back(u);
        else reszta.push_back(u);
    }

    for(auto u : kraw){
        graf[u.a].push_back({u.b, u.dist});
        graf[u.b].push_back({u.a, u.dist});
    }

    int mid = (l + r) / 2;
    dfs3(root, -1, mid, -1);
    for(auto u : reszta){
        //cout << u.l << " " << u.r << " " << u.org << " zap\n";
        sweep.push_back({u.l, u.r, 1, u.org});
    }
    sort(sweep.begin(),sweep.end(),comp);
    ll S = 0;
    for(auto u : sweep){
        if(u.typ == 0){
            akt(u.l, -u.last);
            S += u.last;
        }
        else{
            ans[u.last] = obl(1, u.l, mid, 0, base - 1) + S + 1;
        }
    }
    sweep.clear();
    for(auto u : kraw){
        graf[u.a].clear();
        graf[u.b].clear();
        przedzialy[u.a] = {0, 0};
        przedzialy[u.b] = {0, 0};
    }
    for(int i = l; i <= r; ++i){
        ind[miejsca[i]].clear();
    }

    // cout << l << " " << mid - 1 << " p1\n";
    // cout << mid + 1 << " " << r << " p2\n";
    if(l <= mid - 1) generujkrawedzie(kraw, miejsca[(l + mid - 1) / 2], l, mid - 1);
    vector<d> G1 = szuk;
    if(mid + 1 <= r) generujkrawedzie(kraw, miejsca[(mid + 1 + r) / 2], mid + 1, r);
    vector<d> G2 = szuk;

    
    if(l <= mid - 1) daq(G1, miejsca[(l + mid - 1) / 2], l, mid - 1, lewe);
    if(mid + 1 <= r) daq(G2, miejsca[(mid + 1 + r) / 2], mid + 1, r, prawe);
    return;
}

int main() {
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);
    cin >> n >> m >> q;
    vector<d> kraw;
    int a, b;
    for(int i = 0; i < n-1; ++i){
        cin >> a >> b;
        kraw.push_back({a, b, 1});
    }
    for(int i = 1; i <= m; ++i){
        cin >> miejsca[i];
    }
    vector<e> zap;
    for(int i = 1; i <= q; ++i){
        cin >> a >> b;
        zap.push_back({a, b, i});
    }
    generujkrawedzie(kraw, miejsca[(m+1)/2], 1, m); 
    auto G = szuk;
    daq(G, miejsca[(m + 1) / 2], 1, m, zap);
    for(int i = 1; i <= q; ++i){
        cout << ans[i] << "\n";
    }
    return 0;
}   

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