| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 793245 | vjudge1 | Two Currencies (JOI23_currencies) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std ;
const ll N = (1 << 17) ;
vector<ll> tree ;
vector<pair<ll, ll>> v1, all, v[N + 1] ;
ll l[N + 1], r[N + 1], s[N + 1], t[N + 1], x[N + 1], y[N + 1], dist[N + 1], kol[N + 1], ans[N + 1] ;
ll ind[N + 1], pw[2 * N + 1] ;
ll index[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(ll city, ll last)
{
// cout << city << '\n' ;
ind[city] = v1.size() ;
index[city] = tree.size() ;
tree.push_back(city) ;
v1.push_back({dist[city], city}) ;
for(auto i : v[city])
{
if(i.fi == last)
continue ;
dist[i.fi] = dist[city] + 1 ;
dfs(i.fi, city) ;
// cout << city << '\n' ;
v1.push_back({dist[city], city}) ;
}
kol[city] = (ll)tree.size() - index[city] ;
}
void build_sparce_table()
{
for(ll i = 2 ; i <= v1.size() ; i++)
pw[i] = pw[i / 2] + 1 ;
for(ll i = 0 ; i < v1.size() ; i++)
mn[i][0] = v1[i] ;
for(ll i = 1 ; i < 20 ; i++)
for(ll j = 0 ; j <= (ll)v1.size() - (1 << i) ; j++)
mn[j][i] = min(mn[j][i - 1], mn[j + (1 << (i - 1))][i - 1]) ;
}
ll get_lca(ll a, ll b)
{
a = ind[a] ;
b = ind[b] ;
if(a > b)
swap(a, b) ;
ll 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 dist[a] + dist[b] - dist[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, index[a], {0, 0}, 1), db = get_sum(0, N - 1, index[b], {0, 0}, 1), dlc = get_sum(0, N - 1, index[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 ) ;
ll n, m, q ;
cin >> n >> m >> q ;
for(ll i = 1 ; i < n ; i++)
{
ll a, b ;
cin >> a >> b ;
road.push_back({{a, b}, 0}) ;
}
all.push_back({-1e9, -1e9}) ;
for(ll i = 1 ; i <= m ; i++)
{
ll p, c ;
cin >> p >> c ;
p-- ;
all.push_back({c, p}) ;
road[p].se += c ;
}
sort(all.begin(), all.end()) ;
for(ll i = 1 ; i <= q ; i++)
{
cin >> s[i] >> t[i] >> x[i] >> y[i] ;
l[i] = 0 ;
r[i] = m + 1 ;
ans[i] = -1 ;
}
for(ll 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) ;
// cout<<"___________\n" ;
build_sparce_table() ;
// cout << "kol\n" ;
// for(ll i = 1 ; i <= n ; i++)
// cout << kol[i] << ' ' ;
// cout << '\n' ;
while(true)
{
ll uk = 0 ;
vector<pair<ll, ll>> md ;
// cout << "i l[i] r[i]\n" ;
for(ll i = 1 ; i <= q ; i++)
{
// cout << i << ' ' << l[i] << ' ' << r[i] << '\n' ;
if(l[i] + 1 == r[i])
continue ;
md.push_back({(l[i] + r[i]) >> 1, i}) ;
}
if(!md.size())
break ;
for(ll i = 1 ; i <= m ; i++)
{
pair<ll, ll> p = road[all[i].se].fi ;
ll j ;
if(index[p.fi] < index[p.se])
j = p.se ;
else
j = p.fi ;
// cout << "j index[j] index[j] + kol[j] - 1, all[i].fi\n" ;
// cout << j << ' ' << index[j] << ' ' << index[j] + kol[j] - 1 << ' ' << all[i].fi << "\n" ;
update(0, N - 1, index[j], index[j] + kol[j] - 1, all[i].fi, 1) ;
// cout << "md[uk].fi sn tn xn yn\n" ;
while(uk < md.size() && md[uk].fi == i)
{
ll j = md[uk].se, sn = s[j], tn = t[j], xn = x[j], yn = y[j] ;
// cout << md[uk].fi << ' ' << sn << ' ' << tn << ' ' << xn << ' ' << yn << '\n' ;
pair<ll, ll> gay = get_dist(sn, tn) ;
if(yn - gay.fi >= 0)
{
l[j] = md[uk].fi ;
ans[j] = max(-1ll, xn - (get_kol(sn, tn) - gay.se)) ;
}
else
r[j] = md[uk].fi ;
uk++ ;
}
}
ultra_clear() ;
// cout<<"__________________\n" ;
}
for(ll i = 1 ; i <= q ; i++)
cout << ans[i] << '\n' ;
return 0 ;
}
//5 4 3
//1 2
//1 3
//2 4
//2 5
//2 9
//2 4
//3 5
//4 7
//3 4 2 11
//5 3 4 5
//2 3 1 1