oj.uz

Submission #793269

# Submission time Handle Problem Language Result Execution time Memory
793269 2023-07-25T17:04:02 Z vjudge1 Two Currencies (JOI23_currencies) C++14
10 / 100
 5000 ms 104844 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) ;
//        cout << city << '\n' ;
        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) ;
//    cout<<"___________\n" ;
    build_sparce_table() ;
//    cout << "kol\n" ;
//    for(ll i = 1 ; i <= n ; i++)
//        cout << kol[i] << ' ' ;
//    cout << '\n' ;
    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 ;
//        cout << "i l[i] r[i]\n" ;
        for(ll i = 1 ; i <= q ; i++)
        {
//            cout << i << ' ' << l[i] << ' ' << r[i] << '\n' ;
            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 ;
//            cout << "j soska[j] soska[j] + kol[j] - 1, all[i].fi\n" ;
//            cout << j << ' ' << soska[j] << ' ' << soska[j] + kol[j] - 1 << ' ' << all[i].fi << "\n" ;
            update(0, N - 1, soska[j], soska[j] + kol[j] - 1, all[i].fi, 1) ;
//            cout << "q md[uk].fi sn tn xn yn gay.fi gay.se\n" ;
            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) ;
//                cout << q << ' ' << md[uk].fi << ' ' << sn << ' ' << tn << ' ' << xn << ' ' << yn << ' ' << gay.fi << ' ' << gay.se << '\n' ;
                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() ;
//        cout<<"__________________\n" ;
    }
    for(ll i = 1 ; i <= q ; i++)
        cout << ans[i] << '\n' ;
    return 0 ;
}
//10 7 1
//1 8
//6 3
//5 9
//7 9
//3 1
//3 4
//10 1
//2 6
//5 6
//9 4
//7 4
//7 4
//2 4
//7 4
//7 4
//1 4
//8 6 5 3

Compilation message

currencies.cpp: In function 'void build_sparce_table()':
currencies.cpp:34: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]
   34 |     for(ll i = 2 ; i <= v1.size() ; i++)
      |                    ~~^~~~~~~~~~~~
currencies.cpp:36: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]
   36 |     for(ll i = 0 ; i < v1.size() ; i++)
      |                    ~~^~~~~~~~~~~
currencies.cpp: In function 'int main()':
currencies.cpp:120: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]
  120 |     for(ll j = 0 ; j < road.size() ; j++)
      |                    ~~^~~~~~~~~~~~~
currencies.cpp:161: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]
  161 |             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 1372 ms 9292 KB Output is correct
6 Correct 2190 ms 9444 KB Output is correct
7 Correct 1641 ms 8884 KB Output is correct
8 Correct 2853 ms 9484 KB Output is correct
9 Correct 2781 ms 9476 KB Output is correct
10 Correct 2824 ms 9476 KB Output is correct
11 Correct 2983 ms 9484 KB Output is correct
12 Correct 2994 ms 9484 KB Output is correct
13 Correct 3312 ms 9696 KB Output is correct
14 Correct 3377 ms 9660 KB Output is correct
15 Correct 3444 ms 9588 KB Output is correct
16 Correct 3605 ms 9572 KB Output is correct
17 Correct 3533 ms 9556 KB Output is correct
18 Correct 3618 ms 9568 KB Output is correct
19 Correct 2689 ms 9464 KB Output is correct
20 Correct 2557 ms 9468 KB Output is correct
21 Correct 2605 ms 9472 KB Output is correct
22 Correct 2723 ms 9464 KB Output is correct
23 Correct 2533 ms 9556 KB Output is correct
24 Correct 2299 ms 9484 KB Output is correct
25 Correct 2315 ms 9488 KB Output is correct
26 Correct 2756 ms 9480 KB Output is correct
27 Correct 2520 ms 9480 KB Output is correct
28 Correct 2826 ms 9480 KB Output is correct
29 Correct 525 ms 9464 KB Output is correct
30 Correct 2835 ms 9480 KB Output is correct
31 Correct 2743 ms 9480 KB Output is correct
32 Correct 2658 ms 9476 KB Output is correct
33 Correct 3146 ms 9692 KB Output is correct
34 Correct 3255 ms 9684 KB Output is correct
35 Correct 3244 ms 9684 KB Output is correct

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7488 KB Output is correct
2 Correct 2733 ms 9488 KB Output is correct
3 Correct 2726 ms 9484 KB Output is correct
4 Correct 2637 ms 9480 KB Output is correct
5 Execution timed out 5081 ms 98232 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7508 KB Output is correct
2 Correct 3162 ms 9688 KB Output is correct
3 Correct 3186 ms 9688 KB Output is correct
4 Correct 3147 ms 9684 KB Output is correct
5 Execution timed out 5027 ms 104844 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 1372 ms 9292 KB Output is correct
6 Correct 2190 ms 9444 KB Output is correct
7 Correct 1641 ms 8884 KB Output is correct
8 Correct 2853 ms 9484 KB Output is correct
9 Correct 2781 ms 9476 KB Output is correct
10 Correct 2824 ms 9476 KB Output is correct
11 Correct 2983 ms 9484 KB Output is correct
12 Correct 2994 ms 9484 KB Output is correct
13 Correct 3312 ms 9696 KB Output is correct
14 Correct 3377 ms 9660 KB Output is correct
15 Correct 3444 ms 9588 KB Output is correct
16 Correct 3605 ms 9572 KB Output is correct
17 Correct 3533 ms 9556 KB Output is correct
18 Correct 3618 ms 9568 KB Output is correct
19 Correct 2689 ms 9464 KB Output is correct
20 Correct 2557 ms 9468 KB Output is correct
21 Correct 2605 ms 9472 KB Output is correct
22 Correct 2723 ms 9464 KB Output is correct
23 Correct 2533 ms 9556 KB Output is correct
24 Correct 2299 ms 9484 KB Output is correct
25 Correct 2315 ms 9488 KB Output is correct
26 Correct 2756 ms 9480 KB Output is correct
27 Correct 2520 ms 9480 KB Output is correct
28 Correct 2826 ms 9480 KB Output is correct
29 Correct 525 ms 9464 KB Output is correct
30 Correct 2835 ms 9480 KB Output is correct
31 Correct 2743 ms 9480 KB Output is correct
32 Correct 2658 ms 9476 KB Output is correct
33 Correct 3146 ms 9692 KB Output is correct
34 Correct 3255 ms 9684 KB Output is correct
35 Correct 3244 ms 9684 KB Output is correct
36 Correct 5 ms 7488 KB Output is correct
37 Correct 2733 ms 9488 KB Output is correct
38 Correct 2726 ms 9484 KB Output is correct
39 Correct 2637 ms 9480 KB Output is correct
40 Execution timed out 5081 ms 98232 KB Time limit exceeded
41 Halted 0 ms 0 KB -