Submission #793320

#	Time	Username	Problem	Language	Result	Execution time	Memory
793320		vjudge1	Two Currencies (JOI23_currencies)	C++14	0 / 100	15 ms	19160 KiB

currencies

#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], abubandit[N + 1], kol[N + 1], ans[N + 1] ;
ll ind[N + 1], pw[2 * 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(ll city, ll 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] = (ll)tree.size() - soska[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 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 ) ;
    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++ ;
    }
    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 ;
    }
    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) ;
    build_sparce_table() ;
    for(int i = 1 ; i <= q ; i++)
        ans[i] = max(-1ll, x[i] - get_kol(s[i], t[i])) ;
    for(int z = 0 ; z < 1e5 ; z++)
    {
        ll uk = 0 ;
        vector<pair<ll, ll>> md ;
        for(ll i = 1 ; i <= q ; i++)
        {
            if(l[i] + 1 == r[i])
                continue ;
            md.push_back({(l[i] + r[i]) / 2, i}) ;
        }
        if(!md.size())
            break ;
        for(ll 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++ ;
            }
        }
        if(uk < md.size())cout<<1/0;
        ultra_clear() ;
    }
    for(ll i = 1 ; i <= q ; i++)
        cout << ans[i] << '\n' ;
    return 0 ;
}

Compilation message (stderr)

currencies.cpp: In function 'void build_sparce_table()':
currencies.cpp:33:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for(ll i = 2 ; i <= v1.size() ; i++)
      |                    ~~^~~~~~~~~~~~
currencies.cpp:35:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(ll i = 0 ; i < v1.size() ; i++)
      |                    ~~^~~~~~~~~~~
currencies.cpp: In function 'int main()':
currencies.cpp:119:22: warning: comparison of integer expressions of different signedness: 'long long 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]
  119 |     for(ll j = 0 ; j < road.size() ; j++)
      |                    ~~^~~~~~~~~~~~~
currencies.cpp:150:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |             while(uk < md.size() && md[uk].fi == i)
      |                   ~~~^~~~~~~~~~~
currencies.cpp:164:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |         if(uk < md.size())cout<<1/0;
      |            ~~~^~~~~~~~~~~
currencies.cpp:164:34: warning: division by zero [-Wdiv-by-zero]
  164 |         if(uk < md.size())cout<<1/0;
      |                                 ~^~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 28
• Subtask 3: 0 / 30
• Subtask 4: 0 / 32