oj.uz

Submission #793284

# Submission time Handle Problem Language Result Execution time Memory
793284 2023-07-25T17:18:38 Z vjudge1 Two Currencies (JOI23_currencies) C++
10 / 100
 5000 ms 98836 KB 
#include<bits/stdc++.h>
#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] ;
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] = (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 < 20 ; 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(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 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])) ;
    }
    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:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for(int i = 2 ; i <= v1.size() ; i++)
      |                     ~~^~~~~~~~~~~~
currencies.cpp:35:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i = 0 ; i < v1.size() ; i++)
      |                     ~~^~~~~~~~~~~
currencies.cpp: In function 'int main()':
currencies.cpp:113: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]
  113 |     for(ll j = 0 ; j < road.size() ; j++)
      |                    ~~^~~~~~~~~~~~~
currencies.cpp:149: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]
  149 |             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 5 ms 7492 KB Output is correct
3 Correct 4 ms 7508 KB Output is correct
4 Correct 3 ms 7508 KB Output is correct
5 Correct 1414 ms 9212 KB Output is correct
6 Correct 2172 ms 9448 KB Output is correct
7 Correct 1696 ms 8876 KB Output is correct
8 Correct 3015 ms 9484 KB Output is correct
9 Correct 2785 ms 9476 KB Output is correct
10 Correct 2988 ms 9484 KB Output is correct
11 Correct 2978 ms 9488 KB Output is correct
12 Correct 3065 ms 9476 KB Output is correct
13 Correct 3409 ms 9684 KB Output is correct
14 Correct 3623 ms 9628 KB Output is correct
15 Correct 3534 ms 9572 KB Output is correct
16 Correct 3663 ms 9560 KB Output is correct
17 Correct 3592 ms 9536 KB Output is correct
18 Correct 3609 ms 9556 KB Output is correct
19 Correct 2660 ms 9460 KB Output is correct
20 Correct 2511 ms 9472 KB Output is correct
21 Correct 2553 ms 9464 KB Output is correct
22 Correct 2734 ms 9464 KB Output is correct
23 Correct 2462 ms 9480 KB Output is correct
24 Correct 2303 ms 9488 KB Output is correct
25 Correct 2527 ms 9484 KB Output is correct
26 Correct 2802 ms 9480 KB Output is correct
27 Correct 2786 ms 9472 KB Output is correct
28 Correct 2670 ms 9484 KB Output is correct
29 Correct 520 ms 9464 KB Output is correct
30 Correct 2880 ms 9484 KB Output is correct
31 Correct 2793 ms 9480 KB Output is correct
32 Correct 2699 ms 9480 KB Output is correct
33 Correct 3256 ms 9664 KB Output is correct
34 Correct 3226 ms 9664 KB Output is correct
35 Correct 3165 ms 9664 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 2693 ms 9392 KB Output is correct
3 Correct 2702 ms 9484 KB Output is correct
4 Correct 2652 ms 9476 KB Output is correct
5 Execution timed out 5081 ms 93756 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 3221 ms 9564 KB Output is correct
3 Correct 3110 ms 9664 KB Output is correct
4 Correct 3158 ms 9676 KB Output is correct
5 Execution timed out 5059 ms 98836 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 5 ms 7492 KB Output is correct
3 Correct 4 ms 7508 KB Output is correct
4 Correct 3 ms 7508 KB Output is correct
5 Correct 1414 ms 9212 KB Output is correct
6 Correct 2172 ms 9448 KB Output is correct
7 Correct 1696 ms 8876 KB Output is correct
8 Correct 3015 ms 9484 KB Output is correct
9 Correct 2785 ms 9476 KB Output is correct
10 Correct 2988 ms 9484 KB Output is correct
11 Correct 2978 ms 9488 KB Output is correct
12 Correct 3065 ms 9476 KB Output is correct
13 Correct 3409 ms 9684 KB Output is correct
14 Correct 3623 ms 9628 KB Output is correct
15 Correct 3534 ms 9572 KB Output is correct
16 Correct 3663 ms 9560 KB Output is correct
17 Correct 3592 ms 9536 KB Output is correct
18 Correct 3609 ms 9556 KB Output is correct
19 Correct 2660 ms 9460 KB Output is correct
20 Correct 2511 ms 9472 KB Output is correct
21 Correct 2553 ms 9464 KB Output is correct
22 Correct 2734 ms 9464 KB Output is correct
23 Correct 2462 ms 9480 KB Output is correct
24 Correct 2303 ms 9488 KB Output is correct
25 Correct 2527 ms 9484 KB Output is correct
26 Correct 2802 ms 9480 KB Output is correct
27 Correct 2786 ms 9472 KB Output is correct
28 Correct 2670 ms 9484 KB Output is correct
29 Correct 520 ms 9464 KB Output is correct
30 Correct 2880 ms 9484 KB Output is correct
31 Correct 2793 ms 9480 KB Output is correct
32 Correct 2699 ms 9480 KB Output is correct
33 Correct 3256 ms 9664 KB Output is correct
34 Correct 3226 ms 9664 KB Output is correct
35 Correct 3165 ms 9664 KB Output is correct
36 Correct 4 ms 7508 KB Output is correct
37 Correct 2693 ms 9392 KB Output is correct
38 Correct 2702 ms 9484 KB Output is correct
39 Correct 2652 ms 9476 KB Output is correct
40 Execution timed out 5081 ms 93756 KB Time limit exceeded
41 Halted 0 ms 0 KB -