oj.uz

Submission #793308

# Submission time Handle Problem Language Result Execution time Memory
793308 2023-07-25T17:41:33 Z vjudge1 Two Currencies (JOI23_currencies) C++14
10 / 100
 5000 ms 100576 KB 
#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])) ;
    while(true)
    {
        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]) >> 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(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(ll i = 1 ; i <= q ; i++)
        cout << ans[i] << '\n' ;
    return 0 ;
}

Compilation message

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)
      |                   ~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7508 KB Output is correct
2 Correct 4 ms 7508 KB Output is correct
3 Correct 3 ms 7508 KB Output is correct
4 Correct 4 ms 7508 KB Output is correct
5 Correct 1367 ms 9208 KB Output is correct
6 Correct 2164 ms 9356 KB Output is correct
7 Correct 1615 ms 8796 KB Output is correct
8 Correct 2874 ms 9388 KB Output is correct
9 Correct 2769 ms 9396 KB Output is correct
10 Correct 2851 ms 9420 KB Output is correct
11 Correct 2850 ms 9396 KB Output is correct
12 Correct 2945 ms 9396 KB Output is correct
13 Correct 3229 ms 9608 KB Output is correct
14 Correct 3283 ms 9568 KB Output is correct
15 Correct 3370 ms 9492 KB Output is correct
16 Correct 3532 ms 9480 KB Output is correct
17 Correct 3519 ms 9464 KB Output is correct
18 Correct 3476 ms 9476 KB Output is correct
19 Correct 2475 ms 9380 KB Output is correct
20 Correct 2453 ms 9380 KB Output is correct
21 Correct 2589 ms 9388 KB Output is correct
22 Correct 2636 ms 9380 KB Output is correct
23 Correct 2380 ms 9396 KB Output is correct
24 Correct 2284 ms 9388 KB Output is correct
25 Correct 2265 ms 9388 KB Output is correct
26 Correct 2688 ms 9392 KB Output is correct
27 Correct 2531 ms 9388 KB Output is correct
28 Correct 2702 ms 9388 KB Output is correct
29 Correct 519 ms 9392 KB Output is correct
30 Correct 2745 ms 9388 KB Output is correct
31 Correct 2687 ms 9392 KB Output is correct
32 Correct 2591 ms 9404 KB Output is correct
33 Correct 3095 ms 9592 KB Output is correct
34 Correct 3193 ms 9588 KB Output is correct
35 Correct 3087 ms 9592 KB Output is correct

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7508 KB Output is correct
2 Correct 2683 ms 9388 KB Output is correct
3 Correct 2633 ms 9420 KB Output is correct
4 Correct 2607 ms 9300 KB Output is correct
5 Execution timed out 5074 ms 93932 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7508 KB Output is correct
2 Correct 3097 ms 9596 KB Output is correct
3 Correct 3100 ms 9556 KB Output is correct
4 Correct 3084 ms 9592 KB Output is correct
5 Execution timed out 5060 ms 100576 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7508 KB Output is correct
2 Correct 4 ms 7508 KB Output is correct
3 Correct 3 ms 7508 KB Output is correct
4 Correct 4 ms 7508 KB Output is correct
5 Correct 1367 ms 9208 KB Output is correct
6 Correct 2164 ms 9356 KB Output is correct
7 Correct 1615 ms 8796 KB Output is correct
8 Correct 2874 ms 9388 KB Output is correct
9 Correct 2769 ms 9396 KB Output is correct
10 Correct 2851 ms 9420 KB Output is correct
11 Correct 2850 ms 9396 KB Output is correct
12 Correct 2945 ms 9396 KB Output is correct
13 Correct 3229 ms 9608 KB Output is correct
14 Correct 3283 ms 9568 KB Output is correct
15 Correct 3370 ms 9492 KB Output is correct
16 Correct 3532 ms 9480 KB Output is correct
17 Correct 3519 ms 9464 KB Output is correct
18 Correct 3476 ms 9476 KB Output is correct
19 Correct 2475 ms 9380 KB Output is correct
20 Correct 2453 ms 9380 KB Output is correct
21 Correct 2589 ms 9388 KB Output is correct
22 Correct 2636 ms 9380 KB Output is correct
23 Correct 2380 ms 9396 KB Output is correct
24 Correct 2284 ms 9388 KB Output is correct
25 Correct 2265 ms 9388 KB Output is correct
26 Correct 2688 ms 9392 KB Output is correct
27 Correct 2531 ms 9388 KB Output is correct
28 Correct 2702 ms 9388 KB Output is correct
29 Correct 519 ms 9392 KB Output is correct
30 Correct 2745 ms 9388 KB Output is correct
31 Correct 2687 ms 9392 KB Output is correct
32 Correct 2591 ms 9404 KB Output is correct
33 Correct 3095 ms 9592 KB Output is correct
34 Correct 3193 ms 9588 KB Output is correct
35 Correct 3087 ms 9592 KB Output is correct
36 Correct 4 ms 7508 KB Output is correct
37 Correct 2683 ms 9388 KB Output is correct
38 Correct 2633 ms 9420 KB Output is correct
39 Correct 2607 ms 9300 KB Output is correct
40 Execution timed out 5074 ms 93932 KB Time limit exceeded
41 Halted 0 ms 0 KB -