oj.uz

답안 #793286

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
793286 2023-07-25T17:21:30 Z vjudge1 Two Currencies (JOI23_currencies) C++17
10 / 100
 5000 ms 98772 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 ) ;
    int n, m, q ;
    cin >> n >> m >> q ;
    for(int i = 1 ; i < n ; i++)
    {
        int a, b ;
        cin >> a >> b ;
        road.push_back({{a, b}, 0}) ;
    }
    all.push_back({-1e9, -1e9}) ;
    for(int i = 1 ; i <= m ; i++)
    {
        int p, c ;
        cin >> p >> c ;
        p-- ;
        all.push_back({c, p}) ;
        road[p].se++ ;
    }
    sort(all.begin(), all.end()) ;
    for(int 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)
    {
        int uk = 0 ;
        vector<pair<ll, ll>> md ;
        for(int 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(int 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(int 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:23: warning: comparison of integer expressions of different signedness: '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(int j = 0 ; j < road.size() ; j++)
      |                     ~~^~~~~~~~~~~~~
currencies.cpp:149:22: 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]
  149 |             while(uk < md.size() && md[uk].fi == i)
      |                   ~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 7508 KB Output is correct
2 Correct 3 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 1404 ms 9208 KB Output is correct
6 Correct 2173 ms 9356 KB Output is correct
7 Correct 1630 ms 8796 KB Output is correct
8 Correct 2892 ms 9388 KB Output is correct
9 Correct 2827 ms 9396 KB Output is correct
10 Correct 2846 ms 9384 KB Output is correct
11 Correct 2849 ms 9396 KB Output is correct
12 Correct 2912 ms 9388 KB Output is correct
13 Correct 3215 ms 9576 KB Output is correct
14 Correct 3316 ms 9528 KB Output is correct
15 Correct 3353 ms 9484 KB Output is correct
16 Correct 3403 ms 9460 KB Output is correct
17 Correct 3352 ms 9452 KB Output is correct
18 Correct 3473 ms 9460 KB Output is correct
19 Correct 2440 ms 9388 KB Output is correct
20 Correct 2513 ms 9388 KB Output is correct
21 Correct 2549 ms 9380 KB Output is correct
22 Correct 2591 ms 9428 KB Output is correct
23 Correct 2439 ms 9388 KB Output is correct
24 Correct 2289 ms 9420 KB Output is correct
25 Correct 2225 ms 9388 KB Output is correct
26 Correct 2650 ms 9388 KB Output is correct
27 Correct 2535 ms 9388 KB Output is correct
28 Correct 2759 ms 9392 KB Output is correct
29 Correct 534 ms 9480 KB Output is correct
30 Correct 2718 ms 9476 KB Output is correct
31 Correct 2711 ms 9484 KB Output is correct
32 Correct 2566 ms 9480 KB Output is correct
33 Correct 3127 ms 9660 KB Output is correct
34 Correct 3120 ms 9672 KB Output is correct
35 Correct 3117 ms 9664 KB Output is correct

Subtask #2
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7508 KB Output is correct
2 Correct 2636 ms 9396 KB Output is correct
3 Correct 2635 ms 9480 KB Output is correct
4 Correct 2598 ms 9476 KB Output is correct
5 Execution timed out 5080 ms 93568 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 7508 KB Output is correct
2 Correct 3360 ms 9568 KB Output is correct
3 Correct 3355 ms 9664 KB Output is correct
4 Correct 3212 ms 9660 KB Output is correct
5 Execution timed out 5043 ms 98772 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 7508 KB Output is correct
2 Correct 3 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 1404 ms 9208 KB Output is correct
6 Correct 2173 ms 9356 KB Output is correct
7 Correct 1630 ms 8796 KB Output is correct
8 Correct 2892 ms 9388 KB Output is correct
9 Correct 2827 ms 9396 KB Output is correct
10 Correct 2846 ms 9384 KB Output is correct
11 Correct 2849 ms 9396 KB Output is correct
12 Correct 2912 ms 9388 KB Output is correct
13 Correct 3215 ms 9576 KB Output is correct
14 Correct 3316 ms 9528 KB Output is correct
15 Correct 3353 ms 9484 KB Output is correct
16 Correct 3403 ms 9460 KB Output is correct
17 Correct 3352 ms 9452 KB Output is correct
18 Correct 3473 ms 9460 KB Output is correct
19 Correct 2440 ms 9388 KB Output is correct
20 Correct 2513 ms 9388 KB Output is correct
21 Correct 2549 ms 9380 KB Output is correct
22 Correct 2591 ms 9428 KB Output is correct
23 Correct 2439 ms 9388 KB Output is correct
24 Correct 2289 ms 9420 KB Output is correct
25 Correct 2225 ms 9388 KB Output is correct
26 Correct 2650 ms 9388 KB Output is correct
27 Correct 2535 ms 9388 KB Output is correct
28 Correct 2759 ms 9392 KB Output is correct
29 Correct 534 ms 9480 KB Output is correct
30 Correct 2718 ms 9476 KB Output is correct
31 Correct 2711 ms 9484 KB Output is correct
32 Correct 2566 ms 9480 KB Output is correct
33 Correct 3127 ms 9660 KB Output is correct
34 Correct 3120 ms 9672 KB Output is correct
35 Correct 3117 ms 9664 KB Output is correct
36 Correct 4 ms 7508 KB Output is correct
37 Correct 2636 ms 9396 KB Output is correct
38 Correct 2635 ms 9480 KB Output is correct
39 Correct 2598 ms 9476 KB Output is correct
40 Execution timed out 5080 ms 93568 KB Time limit exceeded
41 Halted 0 ms 0 KB -