| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 793300 | 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<iostream>
#include<algorithm>
#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] ;
ll 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][18] ;
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 < 18 ; 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]) ;
}
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 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(int l, int r, int l1, int r1, ll num, int v)
{
if(l > r1 || r < l1)
return ;
if(l1 <= l && r <= r1)
{
sum[v] += num ;
cnt[v]++ ;
return ;
}
int 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])) ;
}
for(int z = 0 ; z < 20 ; z++)
{
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 ;
}