제출 #1262176

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1262176		SzymonKrzywda	Tourism (JOI23_tourism)	C++20	41 / 100	5022 ms	50596 KiB

tourism

#include <iostream>
#include <vector>
#include <cmath>
#include <map>
#include <unordered_map>
#include <algorithm>

using namespace std;
using vi = vector<int>;
using pii = pair<int, int>;

struct LCA{
    int n, LOG, aktpre;
    vector<vi> graf;
    vector<vi> jump;
    vi preorder;
    vi depth;
    vi max_pre;

    void init(int N, vector<vi> kopia_graf) {
        graf = kopia_graf;
        n = N;
        LOG = ceil(log2(n)) + 1;
        jump.resize(n, vi(LOG, 0));
        depth.resize(n, 0);
        preorder.resize(n, 0);
        aktpre = 0;
        dfs(0, 0);
        preprocess();
    }

    

    void dfs(int v, int p) {
        preorder[v] = aktpre++;
        jump[v][0] = p;
        for (int s : graf[v]) {
            if (p != s) {
                depth[s] = depth[v] + 1;
                dfs(s, v);
            }
        }
    } 

    void preprocess() {
        for (int k = 1; k < LOG; k++) {
            for (int v = 0; v < n; v++) {
                jump[v][k] = jump[jump[v][k - 1]][k - 1];
            }
        }
    }

    int lca(int a, int b) {
        //cout << "Szukam LCA: " << a << ' ' << b << '\n';
        if (a == b) return a;
        if (depth[a] < depth[b]) swap(a, b);

        for (int k = LOG - 1; k >= 0; k--) {
            if (depth[a] - (1 << k) >= depth[b]) a = jump[a][k];
        }
        ////cout << "O koniec 1\n";

        if (a == b) return a;

        for (int k = LOG - 1; k >= 0; k--) {
            if (jump[a][k] != jump[b][k]) {
                a = jump[a][k];
                b = jump[b][k];
            }
        }
       // //cout << "O koniec 2\n";

        return jump[a][0];
    }
};

vi tab;
vi odp;

LCA lca;

const int base = 1 << 19; //sprawdz
int tree[2 * base];

vector<pair<pii, int>> edycje;



void edit(int l, int r, int val) {
    edycje.push_back({{l, r}, val});
    l += base - 1;
    r += base + 1;
    while (l / 2 != r / 2) {
        if (l % 2 == 0) tree[l + 1] += val;
        if (r % 2 == 1) tree[r - 1] += val;
        l /= 2;
        r /= 2;
    }
}   

void clear() {
    while(edycje.size()) {
        auto e = edycje.back();
        edit(e.first.first, e.first.second, -e.second);
        edycje.pop_back();
        edycje.pop_back();
    }
}

int query(int v) {
    v += base;
    int wynik = 0;
    while (v) {
        wynik += tree[v];
        v /= 2;
    }
    return wynik;
}

unordered_map<int, pair<int, int>> mapka;
unordered_map<int, int> waga;
const int MAXN = 1e5; //sprawdz
vector<int> graf[MAXN];

void dfs(int v, int p) {
    if (mapka.find(v) == mapka.end()) mapka[v] = {-1e9, 1e9};
    //cout << "WCHODZE: " << v << ' ' << p << ' ' << graf[v].size() << '\n'; 
    waga[v] = abs(lca.depth[p] - lca.depth[v]);
    for (int s : graf[v]) {
        if (s != p) {
            dfs(s, v);
            mapka[v].first = max(mapka[v].first, mapka[s].first);
            mapka[v].second = min(mapka[v].second, mapka[s].second);
        }
    }
}

bool pre_comp(int a, int b) {
    return lca.preorder[a] < lca.preorder[b];
}



void rec(int l, int r, vector<pair<pii, int>> zap) {
    //cout << "Wchodze: " << l <<  " " << r << ' ' << (l + r) / 2 << '\n'; 
    if (l > r) return;
    vector<pair<pii, int>> lewo;
    vector<pair<pii, int>> prawo;
    vector<pair<pii, int>> srodek;
    int mid = (l + r) / 2;
    for (auto & p : zap) {
        if (p.first.first <= mid && p.first.second >= mid) srodek.push_back(p);
        else if (p.first.second < mid) lewo.push_back(p);
        else prawo.push_back(p);
    }

    //Tworze drzewo virtualne

    vi wierzcholki;
    for (int i = l; i <= r; i++) wierzcholki.push_back(tab[i]);
    sort(wierzcholki.begin(), wierzcholki.end(), pre_comp);
    int ilosc_v = wierzcholki.size();
    for (int i = 0; i < ilosc_v - 1; i++)  wierzcholki.push_back(lca.lca(wierzcholki[i], wierzcholki[i + 1]));
    sort(wierzcholki.begin(), wierzcholki.end(), pre_comp);
    wierzcholki.erase(unique(wierzcholki.begin(), wierzcholki.end()), wierzcholki.end());
    
    for (int v : wierzcholki) graf[v].clear();
    for (int i = 1; i < wierzcholki.size(); i++) {
        int lcaa = lca.lca(wierzcholki[i], wierzcholki[i - 1]);
        graf[lcaa].push_back(wierzcholki[i]);
        graf[wierzcholki[i]].push_back(lcaa);
    }

    // koniec tworzenia

    // for (int i = 0; i < 7; i++) {
    //     //cout << i << ": ";
    //     for (int s : graf[i]) //cout << s << ' ';
    //     //cout << '\n';
    // }


    // liczenie przedzialow
    mapka.clear();
    waga.clear();
    for (int i = l; i <= r; i++) mapka[tab[i]] = {-1e9, 1e9};
    for (int i = l; i <= mid; i++) {
        mapka[tab[i]] = {i, 1e9};
    }
    // for (auto & [k, v] : mapka) {
    //     //cout << k << ' ' << v.first << ' ' << v.second << '\n'; 
    // }

    for (int i = r; i >= mid; i--) {
        mapka[tab[i]] = {mapka[tab[i]].first, i};
    }

    // for (auto & [k, v] : mapka) {
    //     cout << k << ' ' << v.first << ' ' << v.second << '\n'; 
    // }


    dfs(tab[mid], tab[mid]);
    // koniec przedzialow

    // for (auto & [k, v] : mapka) {
    //     cout << k << ' ' << v.first << ' ' << v.second << '\n'; 
    // }

    // wyniki :DDD
    
    
    for (auto & [k, v] : mapka) {
        srodek.push_back({{v.first, 1e9}, k});
        //cout << "OHH: " << k << ' ' << waga[k] << '\n';
        edit(mid, r, waga[k]);
    }
    sort(srodek.begin(), srodek.end());

    
    for (int i = 0; i < srodek.size(); i++) {
        //cout << "Zamiatanie: " << srodek[i].first.first << ' ' << mapka[srodek[i].second].second << ' ' << srodek[i].first.second << ' ' << srodek[i].second << ' ' << waga[srodek[i].second] << '\n';
        if (srodek[i].first.second == 1e9) {
            int koniec = mapka[srodek[i].second].second;
            if (koniec != 1e9) edit(mid, koniec - 1, -waga[srodek[i].second]);
            else edit(mid, r, -waga[srodek[i].second]);
        }
        else {
            odp[srodek[i].second] = query(srodek[i].first.second) + 1;
        }
    }

    clear(); //czyscimy drzewko (Jerzy jesli to czytasz to dam ci 20zl)


    if (l >= r) return;
    rec(l, mid - 1, lewo);
    rec(mid + 1, r, prawo);
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m, q, a, b;
    cin >> n >> m >> q;

    vector<vi> graf(n);
    odp.resize(q);
    tab.resize(m);


    for (int i = 0; i < n - 1; i++) {
        cin >> a >> b;
        a--;
        b--;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }

    lca.init(n, graf);

    for (int i = 0; i < m; i++) {
        cin >> tab[i];
        tab[i]--;
    }

    vector<pair<pii, int>> zap;

    for (int i = 0; i < q; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        zap.push_back({{a, b}, i});
    }


    rec(0, m - 1, zap);

    for (int i = 0; i < q; i++) {
        cout << odp[i] << '\n';
    }


    return 0;
}

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