oj.uz

답안 #793296

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
793296 2023-07-25T17:29:10 Z vjudge1 Two Currencies (JOI23_currencies) C++14
0 / 100
 5000 ms 96632 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std ;
const int N = (1 << 18) ;
vector<int> tree ;
vector<pair<ll, ll>> v1, all, v[N + 1] ;
int l[N + 1], r[N + 1], s[N + 1], t[N + 1] ;
ll x[N + 1], y[N + 1] ;
ll ind[N + 1], pw[2 * N + 1], soska[N + 1] ;
ll dist[N + 1], abubandit[N + 1], kol[N + 1], ans[N + 1] ;
ll sum[2 * N + 1], cnt[2 * N + 1] ;
vector<pair<pair<ll, ll>, ll>> road ;
pair<ll, ll> mn[2 * N + 1][19] ;
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 < 18 ; 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(int l, int r, int l1, int r1, ll num, int 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(int l, int r, int pos, pair<ll, ll> now, int v)
{
    if(l > pos || r < pos)
        return {0, 0} ;
    if(l == r)
        return now ;
    ll mid = (l + r) >> 1 ;
    pair<ll, ll> p1 = get_sum(l, mid, pos, {now.fi + sum[v * 2], now.se + cnt[v * 2]}, v * 2), p2 = get_sum(mid + 1, r, pos, {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(int a, int 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: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 = 2 ; i <= v1.size() ; i++)
      |                     ~~^~~~~~~~~~~~
currencies.cpp:37: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]
   37 |     for(int i = 0 ; i < v1.size() ; i++)
      |                     ~~^~~~~~~~~~~
currencies.cpp: In function 'int main()':
currencies.cpp:115: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]
  115 |     for(int j = 0 ; j < road.size() ; j++)
      |                     ~~^~~~~~~~~~~~~
currencies.cpp:151: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]
  151 |             while(uk < md.size() && md[uk].fi == i)
      |                   ~~~^~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14676 KB Output is correct
2 Correct 10 ms 14676 KB Output is correct
3 Correct 8 ms 14676 KB Output is correct
4 Correct 8 ms 14676 KB Output is correct
5 Correct 3019 ms 16408 KB Output is correct
6 Correct 3269 ms 16552 KB Output is correct
7 Correct 2538 ms 16004 KB Output is correct
8 Correct 4792 ms 16596 KB Output is correct
9 Correct 4059 ms 16588 KB Output is correct
10 Correct 3933 ms 16596 KB Output is correct
11 Correct 4191 ms 16580 KB Output is correct
12 Correct 4451 ms 16488 KB Output is correct
13 Execution timed out 5056 ms 16744 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #2
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 14676 KB Output is correct
2 Correct 3988 ms 16500 KB Output is correct
3 Correct 4509 ms 16496 KB Output is correct
4 Correct 3931 ms 16468 KB Output is correct
5 Execution timed out 5081 ms 96632 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 14720 KB Output is correct
2 Execution timed out 5070 ms 16596 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14676 KB Output is correct
2 Correct 10 ms 14676 KB Output is correct
3 Correct 8 ms 14676 KB Output is correct
4 Correct 8 ms 14676 KB Output is correct
5 Correct 3019 ms 16408 KB Output is correct
6 Correct 3269 ms 16552 KB Output is correct
7 Correct 2538 ms 16004 KB Output is correct
8 Correct 4792 ms 16596 KB Output is correct
9 Correct 4059 ms 16588 KB Output is correct
10 Correct 3933 ms 16596 KB Output is correct
11 Correct 4191 ms 16580 KB Output is correct
12 Correct 4451 ms 16488 KB Output is correct
13 Execution timed out 5056 ms 16744 KB Time limit exceeded
14 Halted 0 ms 0 KB -