#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std ;
const int N = (1 << 17) ;
vector<int> tree ;
vector<pair<ll, ll>> v1, all, v[N + 1] ;
int l[N + 1], r[N + 1], s[N + 1], t[N + 1], x[N + 1], y[N + 1], ind[N + 1], pw[2 * N + 1] ;
ll dist[N + 1], abubandit[N + 1], kol[N + 1], ans[N + 1] ;
ll soska[N + 1], sum[2 * N + 1], cnt[2 * N + 1] ;
vector<pair<pair<ll, ll>, ll>> road ;
pair<ll, ll> mn[2 * N + 1][20] ;
void dfs(int city, int last)
{
ind[city] = v1.size() ;
soska[city] = tree.size() ;
tree.push_back(city) ;
v1.push_back({dist[city], city}) ;
for(auto i : v[city])
{
if(i.fi == last)
continue ;
abubandit[i.fi] = abubandit[city] + i.se ;
dist[i.fi] = dist[city] + 1 ;
dfs(i.fi, city) ;
v1.push_back({dist[city], city}) ;
}
kol[city] = (int)tree.size() - soska[city] ;
}
void build_sparce_table()
{
for(int i = 2 ; i <= v1.size() ; i++)
pw[i] = pw[i / 2] + 1 ;
for(int i = 0 ; i < v1.size() ; i++)
mn[i][0] = v1[i] ;
for(int i = 1 ; i < 20 ; i++)
for(int j = 0 ; j <= (int)v1.size() - (1 << i) ; j++)
mn[j][i] = min(mn[j][i - 1], mn[j + (1 << (i - 1))][i - 1]) ;
}
int get_lca(int a, int b)
{
a = ind[a] ;
b = ind[b] ;
if(a > b)
swap(a, b) ;
int num = pw[b - a + 1] ;
return min(mn[a][num], mn[b - (1 << num) + 1][num]).se ;
}
ll get_kol(ll a, ll b)
{
ll lc = get_lca(a, b) ;
return abubandit[a] + abubandit[b] - abubandit[lc] * 2 ;
}
void ultra_clear()
{
for(ll i = 1 ; i <= 2 * N ; i++)
sum[i] = 0, cnt[i] = 0 ;
}
void update(ll l, ll r, ll l1, ll r1, ll num, ll v)
{
if(l > r1 || r < l1)
return ;
if(l1 <= l && r <= r1)
{
sum[v] += num ;
cnt[v]++ ;
return ;
}
ll mid = (l + r) >> 1 ;
update(l, mid, l1, r1, num, v * 2) ;
update(mid + 1, r, l1, r1, num, v * 2 + 1) ;
}
pair<ll, ll> get_sum(ll l, ll r, ll ind, pair<ll, ll> now, ll v)
{
if(l > ind || r < ind)
return {0, 0} ;
if(l == r)
return now ;
ll mid = (l + r) >> 1 ;
pair<ll, ll> p1 = get_sum(l, mid, ind, {now.fi + sum[v * 2], now.se + cnt[v * 2]}, v * 2), p2 = get_sum(mid + 1, r, ind, {now.fi + sum[v * 2 + 1], now.se + cnt[v * 2 + 1]}, v * 2 + 1) ;
return {p1.fi + p2.fi, p1.se + p2.se} ;
}
pair<ll, ll> get_dist(ll a, ll b)
{
ll lc = get_lca(a, b) ;
pair<ll, ll> da = get_sum(0, N - 1, soska[a], {0, 0}, 1), db = get_sum(0, N - 1, soska[b], {0, 0}, 1), dlc = get_sum(0, N - 1, soska[lc], {0, 0}, 1) ;
return {da.fi + db.fi - dlc.fi * 2, da.se + db.se - dlc.se * 2} ;
}
signed main()
{
ios_base::sync_with_stdio( 0 ) ;
cin.tie( 0 ) ;
cout.tie( 0 ) ;
int n, m, q ;
cin >> n >> m >> q ;
for(int i = 1 ; i < n ; i++)
{
int a, b ;
cin >> a >> b ;
road.push_back({{a, b}, 0}) ;
}
all.push_back({-1e9, -1e9}) ;
for(int i = 1 ; i <= m ; i++)
{
int p, c ;
cin >> p >> c ;
p-- ;
all.push_back({c, p}) ;
road[p].se++ ;
}
sort(all.begin(), all.end()) ;
for(int j = 0 ; j < road.size() ; j++)
{
auto i = road[j] ;
v[i.fi.fi].push_back({i.fi.se, i.se}) ;
v[i.fi.se].push_back({i.fi.fi, i.se}) ;
}
dfs(1, 0) ;
build_sparce_table() ;
for(int i = 1 ; i <= q ; i++)
{
cin >> s[i] >> t[i] >> x[i] >> y[i] ;
l[i] = 0 ;
r[i] = m + 1 ;
ans[i] = max(-1ll, x[i] - get_kol(s[i], t[i])) ;
}
while(true)
{
int uk = 0 ;
vector<pair<ll, ll>> md ;
for(int i = 1 ; i <= q ; i++)
{
if(l[i] + 1 == r[i])
continue ;
md.push_back({(l[i] + r[i]) >> 1, i}) ;
}
if(!md.size())
break ;
for(int i = 1 ; i <= m ; i++)
{
pair<ll, ll> p = road[all[i].se].fi ;
ll j ;
if(soska[p.fi] < soska[p.se])
j = p.se ;
else
j = p.fi ;
update(0, N - 1, soska[j], soska[j] + kol[j] - 1, all[i].fi, 1) ;
while(uk < md.size() && md[uk].fi == i)
{
ll q = md[uk].se, sn = s[q], tn = t[q], xn = x[q], yn = y[q] ;
pair<ll, ll> gay = get_dist(sn, tn) ;
if(yn - gay.fi >= 0)
{
l[q] = md[uk].fi ;
ans[q] = max(-1ll, xn - (get_kol(sn, tn) - gay.se)) ;
}
else
r[q] = md[uk].fi ;
uk++ ;
}
}
ultra_clear() ;
}
for(int i = 1 ; i <= q ; i++)
cout << ans[i] << '\n' ;
return 0 ;
}
Compilation message
currencies.cpp: In function 'void build_sparce_table()':
currencies.cpp:33:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for(int i = 2 ; i <= v1.size() ; i++)
| ~~^~~~~~~~~~~~
currencies.cpp:35:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for(int i = 0 ; i < v1.size() ; i++)
| ~~^~~~~~~~~~~
currencies.cpp: In function 'int main()':
currencies.cpp:113:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | for(int j = 0 ; j < road.size() ; j++)
| ~~^~~~~~~~~~~~~
currencies.cpp:149:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
149 | while(uk < md.size() && md[uk].fi == i)
| ~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
7508 KB |
Output is correct |
| 2 |
Correct |
3 ms |
7508 KB |
Output is correct |
| 3 |
Correct |
3 ms |
7508 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7584 KB |
Output is correct |
| 5 |
Incorrect |
12 ms |
9044 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7508 KB |
Output is correct |
| 2 |
Incorrect |
17 ms |
9300 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
7508 KB |
Output is correct |
| 2 |
Incorrect |
15 ms |
9428 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
7508 KB |
Output is correct |
| 2 |
Correct |
3 ms |
7508 KB |
Output is correct |
| 3 |
Correct |
3 ms |
7508 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7584 KB |
Output is correct |
| 5 |
Incorrect |
12 ms |
9044 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
