#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define lli long long int
#define pll pair<lli,lli>
#define MAX 100000
#define lg 20
//para el vector de orden
#define val first
#define nodo second
//para los c1
#define ss first
#define cc second
struct x{
lli hizq;
lli hder;
lli sum;
lli cant;
};
lli n,m,q,a,b,cont,offset,lastkey,gld,sil,ultpos;
lli anc[MAX+2][lg+2];
vector<lli> hijos[MAX+2],plat;
vector<pll> aristas,orden;
vector<x> stree;
map<lli,lli> raiz;
pll euler[MAX+2];
pll c1,c2,c3,best;
void trip(lli pos, lli padre) {
anc[pos][0] = padre;
lli movil = padre;
rep(i,1,lg) {
anc[pos][i] = anc[movil][i-1];
movil = anc[pos][i];
}
euler[pos].first = cont++;
for (auto h : hijos[pos]) {
if (h == padre) continue;
trip(h,pos);
}
euler[pos].second = cont;
}
void update(lli pos, lli ini , lli fin, lli des, lli v) {
if (ini == fin && ini == des) {
if (v > 0) {stree[pos].cant++; stree[pos].sum += v;}
else {stree[pos].cant--; stree[pos].sum += v;}
/*debugsl(pos);
debugsl(ini);
debugsl(fin);
debug(des);
debugsl(stree[pos].cant);
debug(stree[pos].sum);*/
return;
}
lli mitad = (ini + fin)/2;
if (des <= mitad) {
stree.push_back( stree[stree[pos].hizq] );
stree[pos].hizq = cont;
cont++;
update(stree[pos].hizq, ini, mitad, des, v);
}
else {
stree.push_back( stree[stree[pos].hder] );
stree[pos].hder = cont;
cont++;
update(stree[pos].hder, mitad+1, fin, des, v);
}
stree[pos].sum = stree[ stree[pos].hizq ].sum + stree[ stree[pos].hder ].sum;
stree[pos].cant = stree[ stree[pos].hizq ].cant + stree[ stree[pos].hder ].cant;
/*debugsl(pos);
debugsl(ini);
debugsl(fin);
debug(des);
debugsl(stree[pos].cant);
debug(stree[pos].sum);*/
}
lli lca(lli a, lli b) {
lli movil,r = a;
repa(i,lg,0){
movil = anc[r][i];
if (movil == 0) continue;
if(euler[movil].first <= min(euler[a].first,euler[b].first) && euler[movil].second >= max(euler[a].second,euler[b].second)) continue;
r = movil;
}
if(euler[r].first <= min(euler[a].first,euler[b].first) && euler[r].second >= max(euler[a].second,euler[b].second)) return r;
else return anc[r][0];
}
pll query(lli pos, lli ini, lli fin, lli l, lli r) {
if (ini > r || fin < l) return {0,0};
if (l <= ini && fin <= r) return {stree[pos].sum,stree[pos].cant};
lli mitad = (ini+fin)/2;
pll a = query(stree[pos].hizq, ini, mitad, l, r);
pll b = query(stree[pos].hder, mitad+1, fin, l, r);
a.ss += b.ss;
a.cc += b.cc;
return a;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m >> q;
rep(i,1,n-1) {
cin >> a >> b;
hijos[a].push_back(b);
hijos[b].push_back(a);
aristas.push_back({a,b});
}
cont = 1;
trip(1,0);
rep(i,1,m) {
cin >> a >> b;
if (euler[ aristas[a-1].first ].first < euler[ aristas[a-1].second ].first) a = aristas[a-1].second;
else a = aristas[a-1].first;
orden.push_back({b,a});
plat.push_back(b);
}
sort(orden.begin(), orden.end());
sort(plat.begin(), plat.end());
//correcto
//debug("LLEGUE");
//arma el arbol persistente
cont = 1;
stree.push_back({0,0,0,0});
lastkey = 0;
for(auto act : orden) {
//debug("nuevo");
stree.push_back(stree[lastkey]);
cont++;
raiz[act.val] = cont-1;
lastkey = cont-1;
update(cont-1, 1,n+1, euler[act.nodo].first, act.val);
//debug(stree[lastkey].cant);
//debug(stree[lastkey].cant);
//debug("resta");
stree.push_back(stree[lastkey]);
cont++;
raiz[act.val] = cont-1;
lastkey = cont-1;
update(cont-1, 1,n+1, euler[act.nodo].second, -act.val);
}
//resuelve
rep(Q, 1 , q) {
cin >> a >> b >> gld >> sil;
//debug("nuevo");
lli mitad,k,ini = 1;
lli fin = m;
ultpos = 0;
best = {0,0};
while(ini <= fin) {
mitad = (ini + fin)/2;
k = raiz[ plat[mitad-1] ];
c1 = query(k,1,n+1,1,euler[a].first);
c2 = query(k,1,n+1,1,euler[b].first);
c3 = query(k,1,n+1,1,euler[lca(a,b)].first);
c1.first += c2.first - c3.first;
c1.second += c2.second - c3.second;
if (c1.ss <= sil) {
ultpos = mitad;
best = c1;
ini = mitad+1;
}
else fin = mitad-1;
}
if (ultpos < m) {
ultpos = plat[ultpos];
ultpos = (sil - best.ss)/ultpos;
best.cc += ultpos;
}
c1 = query(lastkey,1,n+1,1,euler[a].first);
c2 = query(lastkey,1,n+1,1,euler[b].first);
c3 = query(lastkey,1,n+1,1,euler[lca(a,b)].first);
c1.first += c2.first - c3.first;
c1.second += c2.second - c3.second;
k = c1.cc - best.cc;
gld -= k;
if (gld >= 0) cout << gld << "\n";
else cout << -1 << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
5460 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
