oj.uz

Submission #793311

# Submission time Handle Problem Language Result Execution time Memory
793311 2023-07-25T17:43:34 Z vjudge1 Two Currencies (JOI23_currencies) C++14
10 / 100
 5000 ms 100604 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])) ;
    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++ ;
            }
        }
        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 5 ms 7508 KB Output is correct
4 Correct 3 ms 7508 KB Output is correct
5 Correct 1366 ms 9216 KB Output is correct
6 Correct 2165 ms 9360 KB Output is correct
7 Correct 1634 ms 8792 KB Output is correct
8 Correct 2786 ms 9392 KB Output is correct
9 Correct 2727 ms 9388 KB Output is correct
10 Correct 2853 ms 9392 KB Output is correct
11 Correct 2809 ms 9392 KB Output is correct
12 Correct 2937 ms 9392 KB Output is correct
13 Correct 3237 ms 9604 KB Output is correct
14 Correct 3196 ms 9568 KB Output is correct
15 Correct 3306 ms 9488 KB Output is correct
16 Correct 3451 ms 9476 KB Output is correct
17 Correct 3328 ms 9460 KB Output is correct
18 Correct 3392 ms 9484 KB Output is correct
19 Correct 2484 ms 9384 KB Output is correct
20 Correct 2401 ms 9388 KB Output is correct
21 Correct 2538 ms 9388 KB Output is correct
22 Correct 2533 ms 9384 KB Output is correct
23 Correct 2322 ms 9388 KB Output is correct
24 Correct 2257 ms 9388 KB Output is correct
25 Correct 2230 ms 9420 KB Output is correct
26 Correct 2684 ms 9412 KB Output is correct
27 Correct 2513 ms 9388 KB Output is correct
28 Correct 2647 ms 9388 KB Output is correct
29 Correct 510 ms 9468 KB Output is correct
30 Correct 2674 ms 9392 KB Output is correct
31 Correct 2628 ms 9396 KB Output is correct
32 Correct 2654 ms 9392 KB Output is correct
33 Correct 3134 ms 9588 KB Output is correct
34 Correct 3225 ms 9596 KB Output is correct
35 Correct 3124 ms 9588 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 2720 ms 9392 KB Output is correct
3 Correct 2721 ms 9392 KB Output is correct
4 Correct 2615 ms 9428 KB Output is correct
5 Execution timed out 5073 ms 93884 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 3075 ms 9592 KB Output is correct
3 Correct 3113 ms 9592 KB Output is correct
4 Correct 3031 ms 9592 KB Output is correct
5 Execution timed out 5064 ms 100604 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 5 ms 7508 KB Output is correct
4 Correct 3 ms 7508 KB Output is correct
5 Correct 1366 ms 9216 KB Output is correct
6 Correct 2165 ms 9360 KB Output is correct
7 Correct 1634 ms 8792 KB Output is correct
8 Correct 2786 ms 9392 KB Output is correct
9 Correct 2727 ms 9388 KB Output is correct
10 Correct 2853 ms 9392 KB Output is correct
11 Correct 2809 ms 9392 KB Output is correct
12 Correct 2937 ms 9392 KB Output is correct
13 Correct 3237 ms 9604 KB Output is correct
14 Correct 3196 ms 9568 KB Output is correct
15 Correct 3306 ms 9488 KB Output is correct
16 Correct 3451 ms 9476 KB Output is correct
17 Correct 3328 ms 9460 KB Output is correct
18 Correct 3392 ms 9484 KB Output is correct
19 Correct 2484 ms 9384 KB Output is correct
20 Correct 2401 ms 9388 KB Output is correct
21 Correct 2538 ms 9388 KB Output is correct
22 Correct 2533 ms 9384 KB Output is correct
23 Correct 2322 ms 9388 KB Output is correct
24 Correct 2257 ms 9388 KB Output is correct
25 Correct 2230 ms 9420 KB Output is correct
26 Correct 2684 ms 9412 KB Output is correct
27 Correct 2513 ms 9388 KB Output is correct
28 Correct 2647 ms 9388 KB Output is correct
29 Correct 510 ms 9468 KB Output is correct
30 Correct 2674 ms 9392 KB Output is correct
31 Correct 2628 ms 9396 KB Output is correct
32 Correct 2654 ms 9392 KB Output is correct
33 Correct 3134 ms 9588 KB Output is correct
34 Correct 3225 ms 9596 KB Output is correct
35 Correct 3124 ms 9588 KB Output is correct
36 Correct 4 ms 7508 KB Output is correct
37 Correct 2720 ms 9392 KB Output is correct
38 Correct 2721 ms 9392 KB Output is correct
39 Correct 2615 ms 9428 KB Output is correct
40 Execution timed out 5073 ms 93884 KB Time limit exceeded
41 Halted 0 ms 0 KB -