| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1262286 | SzymonKrzywda | Two Currencies (JOI23_currencies) | C++20 | 0 ms | 0 KiB |
#include <iostream>
using namespace std;
using vi = vector<int>;
using pii = pair<int, int>;
#define ff first
#define ss second
#define int long long
const int MAXN = 1e5 + 7;
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.assign(n, vi(LOG, 0));
depth.assign(n, 0);
preorder.assign(n, 0);
max_pre.assign(n, 0);
aktpre = 0;
dfs(0, 0);
preprocess();
}
void dfs(int v, int p) {
preorder[v] = aktpre++;
max_pre[v] = preorder[v];
jump[v][0] = p;
for (int s : graf[v]) {
if (p != s) {
depth[s] = depth[v] + 1;
dfs(s, v);
max_pre[v] = max(max_pre[v], max_pre[s]);
}
}
}
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];
}
};
const int base = 1 << 17;
vector<int> tree;
vector<int> tree2;
void add(int l, int r, int val = 1) {
l += base - 1;
r += base + 1;
while (l / 2 != r / 2) {
if (l % 2 == 0) {
tree[l + 1] += val;
tree2[l + 1] ++;
}
if (r % 2 == 1) {
tree[r - 1] += val;
tree2[r - 1] ++;
}
l /= 2;
r /= 2;
}
}
pii query(int v) {
v += base;
int ans = 0;
int ans2 = 0;
while (v) {
ans += tree[v];
ans2 += tree2[v];
v /= 2;
}
return {ans, ans2};
}
LCA lca;
struct zap{
int a, b, g, s, idx, left, right, mid, koszts, ile;
};
bool comps(zap a, zap b) {
return a.s < b.s;
}
bool comp_bin(zap a, zap b) {
if (a.mid == b.mid) return a.idx < b.idx;
return a.mid < b.mid;
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m, q, a, b;
cin >> n >> m >> q;
vector<vi> graf(n);
vector<pii> kra;
vi ile_bramek(n + 2, 0);
for (int i = 0; i < n - 1; i++) {
cin >> a >> b;
a--;
b--;
graf[a].push_back(b);
graf[b].push_back(a);
kra.push_back({a, b});
}
lca.init(n, graf);
vector<zap> tab_zap;
for (int i = 0; i < m; i++) {
cin >> a >> b;
a--;
zap z;
z.a = kra[a].first;
z.b = kra[a].second;
if (lca.depth[z.a] > lca.depth[z.b]) swap(z.a, z.b);
ile_bramek[lca.preorder[z.b]] ++;
ile_bramek[lca.max_pre[z.b] + 1] --;
z.idx = -1;
z.mid = b;
z.s = b;
tab_zap.push_back(z);
}
sort(tab_zap.begin(), tab_zap.end(), comps);
for (int i = 0; i < m; i++) {
tab_zap[i].mid = i;
}
for (int i = 1; i < n + 2; i++) ile_bramek[i] += ile_bramek[i - 1];
lca.init(n, graf);
for (int i = 0; i < q; i++) {
zap z;
cin >> z.a >> z.b >> z.g >> z.s;
z.a--;
z.b--;
z.idx = i;
z.left = -1;
z.right = m - 1;
z.mid = (z.left + z.right + 1) / 2;
tab_zap.push_back(z);
}
vi odp(q, -1);
for (int i = 0; i < 25; i++) {
//cout << "UWU\n";
tree.assign(2 * base, 0);
tree2.assign(2 * base, 0);
sort(tab_zap.begin(), tab_zap.end(), comp_bin);
for (auto & z : tab_zap) {
//if (z.idx == -1) cout << "Dodaje bariere: " << z.a << ' ' << z.b << ' ' << z.g << ' ' << z.s << ' ' << z.mid << '\n';
//else cout << "Zapytanie: " << z.a << ' ' << z.b << ' ' << z.idx << ' ' << z.left << ' ' << z.right << ' ' << z.mid << '\n';
if (z.idx == -1) {
add(lca.preorder[z.b], lca.max_pre[z.b], z.s);
}
else {
int prea = lca.preorder[z.a];
int preb = lca.preorder[z.b];
int lcaa = lca.lca(z.a, z.b);
int prelca = lca.preorder[lcaa];
//cout << query(prea).first << ' ' << query(preb).first << ' ' << query(prelca).first << '\n';
long long koszt = query(prea).first + query(preb).first - 2 * query(prelca).first;
z.koszts = koszt;
z.ile = ile_bramek[prea] + ile_bramek[preb] - 2 * ile_bramek[prelca] - (query(prea).second + query(preb).second - 2 * query(prelca).second);
if (koszt <= z.s) z.left = z.mid;
else z.right = z.mid - 1;
z.mid = (z.left + z.right + 1) / 2;
// cout << "KOSZT: " << koszt << ' ' << z.ile << '\n';
if (z.left == -1 && z.right == -1) z.mid = -1;
if (z.koszts <= z.s && z.ile <= z.g) odp[z.idx] = z.g - z.ile;
else odp[z.idx] = -1;
}
}
}
for (int i = 0; i < q; i++) {
cout << odp[i] << '\n';
}
return 0;
}
/*
3 2 1
2 1
3 2
2 1
1 1
1 2 1 1*/