oj.uz

Submission #793322

# Submission time Handle Problem Language Result Execution time Memory
793322 2023-07-25T17:51:07 Z vjudge1 Two Currencies (JOI23_currencies) C++14
100 / 100
 2760 ms 112436 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]) / 2, i}) ;
        }
        sort(md.begin(), md.end()) ;
        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:151: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]
  151 |             while(uk < md.size() && md[uk].fi == i)
      |                   ~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 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 3 ms 7508 KB Output is correct
5 Correct 14 ms 9172 KB Output is correct
6 Correct 19 ms 9300 KB Output is correct
7 Correct 16 ms 8812 KB Output is correct
8 Correct 20 ms 9392 KB Output is correct
9 Correct 20 ms 9408 KB Output is correct
10 Correct 20 ms 9300 KB Output is correct
11 Correct 20 ms 9300 KB Output is correct
12 Correct 24 ms 9300 KB Output is correct
13 Correct 21 ms 9556 KB Output is correct
14 Correct 21 ms 9540 KB Output is correct
15 Correct 21 ms 9428 KB Output is correct
16 Correct 26 ms 9484 KB Output is correct
17 Correct 21 ms 9488 KB Output is correct
18 Correct 26 ms 9472 KB Output is correct
19 Correct 19 ms 9300 KB Output is correct
20 Correct 19 ms 9348 KB Output is correct
21 Correct 19 ms 9404 KB Output is correct
22 Correct 19 ms 9404 KB Output is correct
23 Correct 19 ms 9396 KB Output is correct
24 Correct 22 ms 9300 KB Output is correct
25 Correct 18 ms 9300 KB Output is correct
26 Correct 17 ms 9308 KB Output is correct
27 Correct 17 ms 9416 KB Output is correct
28 Correct 17 ms 9408 KB Output is correct
29 Correct 17 ms 9408 KB Output is correct
30 Correct 27 ms 9416 KB Output is correct
31 Correct 19 ms 9416 KB Output is correct
32 Correct 19 ms 9428 KB Output is correct
33 Correct 20 ms 9608 KB Output is correct
34 Correct 21 ms 9524 KB Output is correct
35 Correct 25 ms 9636 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7508 KB Output is correct
2 Correct 20 ms 9412 KB Output is correct
3 Correct 19 ms 9412 KB Output is correct
4 Correct 19 ms 9412 KB Output is correct
5 Correct 1212 ms 94284 KB Output is correct
6 Correct 1645 ms 71700 KB Output is correct
7 Correct 1534 ms 83404 KB Output is correct
8 Correct 1235 ms 85164 KB Output is correct
9 Correct 1181 ms 83412 KB Output is correct
10 Correct 2080 ms 98876 KB Output is correct
11 Correct 2072 ms 98876 KB Output is correct
12 Correct 2111 ms 98876 KB Output is correct
13 Correct 2017 ms 98876 KB Output is correct
14 Correct 1941 ms 98888 KB Output is correct
15 Correct 1994 ms 109212 KB Output is correct
16 Correct 2083 ms 109900 KB Output is correct
17 Correct 1983 ms 109016 KB Output is correct
18 Correct 2058 ms 99216 KB Output is correct
19 Correct 2107 ms 99264 KB Output is correct
20 Correct 2087 ms 99320 KB Output is correct
21 Correct 1822 ms 98304 KB Output is correct
22 Correct 1818 ms 98304 KB Output is correct
23 Correct 1776 ms 98308 KB Output is correct
24 Correct 1714 ms 98372 KB Output is correct
25 Correct 1541 ms 98996 KB Output is correct
26 Correct 1584 ms 99004 KB Output is correct
27 Correct 1538 ms 98876 KB Output is correct
28 Correct 1105 ms 98920 KB Output is correct
29 Correct 1093 ms 98752 KB Output is correct
30 Correct 1187 ms 98868 KB Output is correct
31 Correct 1223 ms 98880 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7508 KB Output is correct
2 Correct 21 ms 9620 KB Output is correct
3 Correct 21 ms 9556 KB Output is correct
4 Correct 20 ms 9556 KB Output is correct
5 Correct 1330 ms 101032 KB Output is correct
6 Correct 1395 ms 101836 KB Output is correct
7 Correct 1710 ms 68560 KB Output is correct
8 Correct 2269 ms 111576 KB Output is correct
9 Correct 2469 ms 111552 KB Output is correct
10 Correct 2760 ms 111796 KB Output is correct
11 Correct 2081 ms 112056 KB Output is correct
12 Correct 2554 ms 112056 KB Output is correct
13 Correct 2184 ms 112052 KB Output is correct
14 Correct 1670 ms 112308 KB Output is correct
15 Correct 1595 ms 112312 KB Output is correct
16 Correct 1705 ms 112312 KB Output is correct
17 Correct 1668 ms 112436 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 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 3 ms 7508 KB Output is correct
5 Correct 14 ms 9172 KB Output is correct
6 Correct 19 ms 9300 KB Output is correct
7 Correct 16 ms 8812 KB Output is correct
8 Correct 20 ms 9392 KB Output is correct
9 Correct 20 ms 9408 KB Output is correct
10 Correct 20 ms 9300 KB Output is correct
11 Correct 20 ms 9300 KB Output is correct
12 Correct 24 ms 9300 KB Output is correct
13 Correct 21 ms 9556 KB Output is correct
14 Correct 21 ms 9540 KB Output is correct
15 Correct 21 ms 9428 KB Output is correct
16 Correct 26 ms 9484 KB Output is correct
17 Correct 21 ms 9488 KB Output is correct
18 Correct 26 ms 9472 KB Output is correct
19 Correct 19 ms 9300 KB Output is correct
20 Correct 19 ms 9348 KB Output is correct
21 Correct 19 ms 9404 KB Output is correct
22 Correct 19 ms 9404 KB Output is correct
23 Correct 19 ms 9396 KB Output is correct
24 Correct 22 ms 9300 KB Output is correct
25 Correct 18 ms 9300 KB Output is correct
26 Correct 17 ms 9308 KB Output is correct
27 Correct 17 ms 9416 KB Output is correct
28 Correct 17 ms 9408 KB Output is correct
29 Correct 17 ms 9408 KB Output is correct
30 Correct 27 ms 9416 KB Output is correct
31 Correct 19 ms 9416 KB Output is correct
32 Correct 19 ms 9428 KB Output is correct
33 Correct 20 ms 9608 KB Output is correct
34 Correct 21 ms 9524 KB Output is correct
35 Correct 25 ms 9636 KB Output is correct
36 Correct 3 ms 7508 KB Output is correct
37 Correct 20 ms 9412 KB Output is correct
38 Correct 19 ms 9412 KB Output is correct
39 Correct 19 ms 9412 KB Output is correct
40 Correct 1212 ms 94284 KB Output is correct
41 Correct 1645 ms 71700 KB Output is correct
42 Correct 1534 ms 83404 KB Output is correct
43 Correct 1235 ms 85164 KB Output is correct
44 Correct 1181 ms 83412 KB Output is correct
45 Correct 2080 ms 98876 KB Output is correct
46 Correct 2072 ms 98876 KB Output is correct
47 Correct 2111 ms 98876 KB Output is correct
48 Correct 2017 ms 98876 KB Output is correct
49 Correct 1941 ms 98888 KB Output is correct
50 Correct 1994 ms 109212 KB Output is correct
51 Correct 2083 ms 109900 KB Output is correct
52 Correct 1983 ms 109016 KB Output is correct
53 Correct 2058 ms 99216 KB Output is correct
54 Correct 2107 ms 99264 KB Output is correct
55 Correct 2087 ms 99320 KB Output is correct
56 Correct 1822 ms 98304 KB Output is correct
57 Correct 1818 ms 98304 KB Output is correct
58 Correct 1776 ms 98308 KB Output is correct
59 Correct 1714 ms 98372 KB Output is correct
60 Correct 1541 ms 98996 KB Output is correct
61 Correct 1584 ms 99004 KB Output is correct
62 Correct 1538 ms 98876 KB Output is correct
63 Correct 1105 ms 98920 KB Output is correct
64 Correct 1093 ms 98752 KB Output is correct
65 Correct 1187 ms 98868 KB Output is correct
66 Correct 1223 ms 98880 KB Output is correct
67 Correct 4 ms 7508 KB Output is correct
68 Correct 21 ms 9620 KB Output is correct
69 Correct 21 ms 9556 KB Output is correct
70 Correct 20 ms 9556 KB Output is correct
71 Correct 1330 ms 101032 KB Output is correct
72 Correct 1395 ms 101836 KB Output is correct
73 Correct 1710 ms 68560 KB Output is correct
74 Correct 2269 ms 111576 KB Output is correct
75 Correct 2469 ms 111552 KB Output is correct
76 Correct 2760 ms 111796 KB Output is correct
77 Correct 2081 ms 112056 KB Output is correct
78 Correct 2554 ms 112056 KB Output is correct
79 Correct 2184 ms 112052 KB Output is correct
80 Correct 1670 ms 112308 KB Output is correct
81 Correct 1595 ms 112312 KB Output is correct
82 Correct 1705 ms 112312 KB Output is correct
83 Correct 1668 ms 112436 KB Output is correct
84 Correct 1437 ms 84532 KB Output is correct
85 Correct 1487 ms 62488 KB Output is correct
86 Correct 1316 ms 61660 KB Output is correct
87 Correct 2316 ms 101564 KB Output is correct
88 Correct 2342 ms 101568 KB Output is correct
89 Correct 2226 ms 101568 KB Output is correct
90 Correct 2158 ms 101564 KB Output is correct
91 Correct 2163 ms 101548 KB Output is correct
92 Correct 2399 ms 108588 KB Output is correct
93 Correct 2346 ms 111328 KB Output is correct
94 Correct 2364 ms 102028 KB Output is correct
95 Correct 2308 ms 102048 KB Output is correct
96 Correct 2523 ms 102028 KB Output is correct
97 Correct 2600 ms 101996 KB Output is correct
98 Correct 2171 ms 100992 KB Output is correct
99 Correct 2057 ms 101076 KB Output is correct
100 Correct 2075 ms 101028 KB Output is correct
101 Correct 2054 ms 100996 KB Output is correct
102 Correct 1778 ms 101568 KB Output is correct
103 Correct 1735 ms 101564 KB Output is correct
104 Correct 1754 ms 101564 KB Output is correct
105 Correct 1217 ms 101548 KB Output is correct
106 Correct 1179 ms 101440 KB Output is correct
107 Correct 1306 ms 101304 KB Output is correct
108 Correct 1313 ms 101304 KB Output is correct