| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1262158 | SzymonKrzywda | Tourism (JOI23_tourism) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
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 = mid; i <= r; 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
//cout << query(5) << '\n';
for (auto & [k, v] : mapka) {
srodek.push_back({{v.first, 1e9}, k});
//cout << "OHH: " << 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 {
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;
}