oj.uz

Submission #980349

# Submission time Handle Problem Language Result Execution time Memory
980349 2024-05-12T05:46:18 Z hasan2006 Swapping Cities (APIO20_swap) C++17
100 / 100
 516 ms 138420 KB 
#include "swap.h"
#include <bits/stdc++.h>

using namespace std;

#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define se second
#define fi first
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"


const int N =2e5 + 9 , mod = 1e9 + 7;
ll  p[N], sz[N] , a[N] , b[N] , dp[N] ,  dp1[N] ,  c[N][25] , d[N] , par[N][25] , mx[N][25] , us[N] , us1[N];
vector<pair<ll,ll>>v[N] , v1[N] , vc[N] ,  vv[N];
int get(int x){
    return (p[x] == x ? x : get(p[x]));
}
void join(int X , int Y , ll k){
    int x = get(X) , y = get(Y);
    if(x != y){
        if(sz[x] < sz[y])
            swap(x , y);
        p[y] = x;
        sz[x] += sz[y];
        vv[X].pb({k , Y});
        vv[Y].pb({k , X});
    }else {
        v1[X].pb({k , Y});
        v1[Y].pb({k , X});
    }
}
ll timer = 0;

void dd(int n  ,int p = 0 , int k = 0){
    if(p)
        v[p].pb({k , n});
    for(auto to : vv[n])
        if(to.se != p)
            dd(to.se , n , to.fi);
}

void dfs(int n , int p = 0 , ll k = 1e18){
    par[n][0] = p;
    if(v[p].size())
        c[n][0] = v[p][0].fi;
    else
        c[n][0] = 1e18;
    if(v[p].size() && v[p][0].se == n){
        if(v[p].size() > 1)
            c[n][0] = v[p][1].fi;
        else
            c[n][0] = 1e18;
    }
    if(v1[p].size())
        c[n][0] = min(c[n][0] , v1[p][0].fi);
    if(v1[n].size())
        c[n][0] = min(c[n][0] , v1[n][0].fi);
    mx[n][0] = k;
    us[n] = ++timer;
    for(int i = 1; i <= 20; i++){
        par[n][i] = par[par[n][i - 1]][i - 1] ;
        mx[n][i] = max(mx[n][i - 1] , mx[par[n][i - 1]][i - 1]);
        c[n][i] = min(c[n][i - 1] , c[par[n][i - 1]][i - 1]);
    }
    for(auto to : v[n])
        dfs(to.se , n , to.fi);
    if(v1[n].size())
        dp[n] = min(dp[n] , v1[n][0].fi);
    if(v[n].size() > 1)
        dp[n] = min(dp[n] , v[n][1].fi);
    dp[p] = min(dp[p] , max(k , dp[n]));
    us1[n] = ++timer;
}
void dfs1(int n , int p = 0 , ll k = 1e18 , ll ans = 1e18){
    if(v1[n].size())
        ans = min(ans , v1[n][0].fi);
    dp1[n] = ans;
    v[n].pb({k , p});
    for(auto to : v[n])
        if(to.se != p)
            vc[n].pb({max(to.fi , dp[to.se]) , to.se});
    sort(all(v[n]));
    sort(all(vc[n]));
    for(auto to : v[n]){
        if(to.se != p){
            ll ans1 = ans;
            if(v[n].size() >= 3){
                if(v[n][1].se == to.se || v[n][0].se == to.se)
                    ans1 = min(ans1, v[n][2].fi);
                else
                    ans1 = min(ans1 , v[n][1].fi);
            }
            if(vc[n][0].se != to.se)
                ans1 = min(ans1 ,vc[n][0].fi);
            else if(vc[n].size() > 1)
                ans1 = min(ans1 , vc[n][1].fi);
            dfs1(to.se , n , to.fi , max(ans1 , to.fi));
        }
    }
}

bool ok(int u, int v)
{
    return (u == 0 || (us[u] <= us[v] && us1[u] >= us1[v]));
}

ll get(int x , int y){
    ll mn = 1e18 , ans = 0;
    mn = min({mn , dp[y]});
    for(int i = 18; i >= 0; i--){
        if(!ok(par[y][i] , x)){
            mn = min(mn , c[y][i]);
            ans = max(ans , mx[y][i]);
            y = par[y][i];
        }
    }
    ans = max(ans , mx[y][0]);
    mn = min({mn , dp1[y]});
    ans = max(ans , mn);
    y = par[y][0];
    if(v1[y].size())
        mn = min(mn , v1[y][0].fi);
    if(ans > 1e9)
        ans = -1;
    return ans;
}
ll mm = 0;
ll lca(int x , int y){

    if(ok(x , y)){
        return get(x , y);
    }
    if(ok(y , x))
        return get(y , x);
    ll mn = 1e18 , ans = 0;
    mn = min({mn , dp[x] , dp[y]});
    for(int i = 18; i >= 0; i--){
        if(!ok(par[y][i] , x)){
                mn = min(mn , c[y][i]);
                ans = max(ans , mx[y][i]);
                y = par[y][i];
            }
        }
    for(int i = 18; i >= 0; i--){
            if(!ok(par[x][i] , y)){
                mn = min(mn , c[x][i]);
                ans = max(ans , mx[x][i]);
                x = par[x][i];
            }
    }
    ans = max(ans , mx[x][0]);
    ans = max(ans , mx[y][0]);
    for(int i = 0; i < 3 && i < v[par[x][0]].size(); i++)
        if(v[par[x][0]][i].se != x && v[par[x][0]][i].se != y)
            mn = min(mn ,v[par[x][0]][i].fi);
    x = par[x][0];
    if(v1[x].size())
        mn = min(mn , v1[x][0].fi);
    ans = max(ans , mn);
    if(ans > 1e9)
        ans = -1;
    return ans;
}

void init(int n , int m , vector<int>v , vector<int>u , vector<int>c)
{
    vector<pair<ll,pair<ll,ll>>>vc;
    for(int i = 0; i <= n; i++)
        dp[i] = 1e18 , p[i] =  i , sz[i] = 1;
    for(int i = 0; i < m; i++)
        vc.pb({c[i] , {v[i] + 1, u[i] + 1}});
    sort(all(vc));
    for(auto to : vc)
        join(to.se.fi , to.se.se , to.fi);
    dd(1);
   for(int i = 1; i <= n ; i++)
        sort(all(::v[i])) , sort(all(::v1[i]));
    dfs(1);
    dfs1(1);
}


int getMinimumFuelCapacity(int l, int r) {
        l++ , r++;
        return lca(l , r);
}
/*
int main(){

    init(4, 4, {0, 0, 1 , 2}, {1 , 3 , 2 , 3}, {1 , 3 , 2 , 4});
    cout<<getMinimumFuelCapacity(0,1)<<"\n";
    cout<<getMinimumFuelCapacity(0,2)<<"\n";
    cout<<getMinimumFuelCapacity(0,3)<<"\n";
    cout<<getMinimumFuelCapacity(1,2)<<"\n";
    cout<<getMinimumFuelCapacity(1,3)<<"\n";
    cout<<getMinimumFuelCapacity(2,3)<<"\n";
}*/

Compilation message

swap.cpp: In function 'long long int lca(int, int)':
swap.cpp:164:31: 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]
  164 |     for(int i = 0; i < 3 && i < v[par[x][0]].size(); i++)
      |                             ~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35416 KB Output is correct
2 Correct 6 ms 35420 KB Output is correct
3 Correct 6 ms 35420 KB Output is correct
4 Correct 7 ms 35548 KB Output is correct
5 Correct 7 ms 35528 KB Output is correct
6 Correct 7 ms 35676 KB Output is correct
7 Correct 7 ms 35676 KB Output is correct
8 Correct 7 ms 35676 KB Output is correct
9 Correct 137 ms 102172 KB Output is correct
10 Correct 167 ms 117076 KB Output is correct
11 Correct 174 ms 116160 KB Output is correct
12 Correct 178 ms 123840 KB Output is correct
13 Correct 172 ms 126660 KB Output is correct
14 Correct 146 ms 101324 KB Output is correct
15 Correct 393 ms 118140 KB Output is correct
16 Correct 368 ms 115036 KB Output is correct
17 Correct 430 ms 128144 KB Output is correct
18 Correct 408 ms 125876 KB Output is correct
19 Correct 100 ms 55512 KB Output is correct
20 Correct 375 ms 117268 KB Output is correct
21 Correct 396 ms 114848 KB Output is correct
22 Correct 414 ms 124604 KB Output is correct
23 Correct 410 ms 125132 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35416 KB Output is correct
2 Correct 6 ms 35420 KB Output is correct
3 Correct 200 ms 107180 KB Output is correct
4 Correct 207 ms 114108 KB Output is correct
5 Correct 213 ms 107388 KB Output is correct
6 Correct 190 ms 112020 KB Output is correct
7 Correct 203 ms 107712 KB Output is correct
8 Correct 202 ms 107056 KB Output is correct
9 Correct 206 ms 108204 KB Output is correct
10 Correct 191 ms 106800 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35416 KB Output is correct
2 Correct 6 ms 35420 KB Output is correct
3 Correct 6 ms 35420 KB Output is correct
4 Correct 7 ms 35548 KB Output is correct
5 Correct 7 ms 35528 KB Output is correct
6 Correct 7 ms 35676 KB Output is correct
7 Correct 7 ms 35676 KB Output is correct
8 Correct 7 ms 35676 KB Output is correct
9 Correct 6 ms 35416 KB Output is correct
10 Correct 7 ms 35676 KB Output is correct
11 Correct 8 ms 35500 KB Output is correct
12 Correct 7 ms 35688 KB Output is correct
13 Correct 7 ms 35420 KB Output is correct
14 Correct 7 ms 35420 KB Output is correct
15 Correct 8 ms 35676 KB Output is correct
16 Correct 7 ms 35672 KB Output is correct
17 Correct 7 ms 35676 KB Output is correct
18 Correct 7 ms 35420 KB Output is correct
19 Correct 7 ms 35420 KB Output is correct
20 Correct 7 ms 35712 KB Output is correct
21 Correct 7 ms 35928 KB Output is correct
22 Correct 7 ms 35604 KB Output is correct
23 Correct 7 ms 35420 KB Output is correct
24 Correct 7 ms 35676 KB Output is correct
25 Correct 8 ms 35772 KB Output is correct
26 Correct 9 ms 35676 KB Output is correct
27 Correct 8 ms 35932 KB Output is correct
28 Correct 8 ms 35676 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35416 KB Output is correct
2 Correct 6 ms 35416 KB Output is correct
3 Correct 6 ms 35420 KB Output is correct
4 Correct 6 ms 35420 KB Output is correct
5 Correct 7 ms 35548 KB Output is correct
6 Correct 7 ms 35528 KB Output is correct
7 Correct 7 ms 35676 KB Output is correct
8 Correct 7 ms 35676 KB Output is correct
9 Correct 7 ms 35676 KB Output is correct
10 Correct 137 ms 102172 KB Output is correct
11 Correct 167 ms 117076 KB Output is correct
12 Correct 174 ms 116160 KB Output is correct
13 Correct 178 ms 123840 KB Output is correct
14 Correct 172 ms 126660 KB Output is correct
15 Correct 7 ms 35676 KB Output is correct
16 Correct 8 ms 35500 KB Output is correct
17 Correct 7 ms 35688 KB Output is correct
18 Correct 7 ms 35420 KB Output is correct
19 Correct 7 ms 35420 KB Output is correct
20 Correct 8 ms 35676 KB Output is correct
21 Correct 7 ms 35672 KB Output is correct
22 Correct 7 ms 35676 KB Output is correct
23 Correct 7 ms 35420 KB Output is correct
24 Correct 7 ms 35420 KB Output is correct
25 Correct 7 ms 35712 KB Output is correct
26 Correct 7 ms 35928 KB Output is correct
27 Correct 7 ms 35604 KB Output is correct
28 Correct 7 ms 35420 KB Output is correct
29 Correct 7 ms 35676 KB Output is correct
30 Correct 8 ms 35772 KB Output is correct
31 Correct 9 ms 35676 KB Output is correct
32 Correct 8 ms 35932 KB Output is correct
33 Correct 8 ms 35676 KB Output is correct
34 Correct 19 ms 43864 KB Output is correct
35 Correct 178 ms 123080 KB Output is correct
36 Correct 165 ms 119428 KB Output is correct
37 Correct 162 ms 115908 KB Output is correct
38 Correct 146 ms 110976 KB Output is correct
39 Correct 136 ms 110016 KB Output is correct
40 Correct 124 ms 106948 KB Output is correct
41 Correct 179 ms 120120 KB Output is correct
42 Correct 171 ms 121980 KB Output is correct
43 Correct 162 ms 123764 KB Output is correct
44 Correct 147 ms 115340 KB Output is correct
45 Correct 153 ms 108212 KB Output is correct
46 Correct 161 ms 119188 KB Output is correct
47 Correct 146 ms 114564 KB Output is correct
48 Correct 134 ms 111040 KB Output is correct
49 Correct 68 ms 55736 KB Output is correct
50 Correct 60 ms 56004 KB Output is correct
51 Correct 134 ms 92504 KB Output is correct
52 Correct 207 ms 128308 KB Output is correct
53 Correct 218 ms 127776 KB Output is correct
54 Correct 256 ms 133864 KB Output is correct
55 Correct 166 ms 127676 KB Output is correct
56 Correct 191 ms 126152 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35416 KB Output is correct
2 Correct 6 ms 35420 KB Output is correct
3 Correct 6 ms 35420 KB Output is correct
4 Correct 7 ms 35548 KB Output is correct
5 Correct 7 ms 35528 KB Output is correct
6 Correct 7 ms 35676 KB Output is correct
7 Correct 7 ms 35676 KB Output is correct
8 Correct 7 ms 35676 KB Output is correct
9 Correct 137 ms 102172 KB Output is correct
10 Correct 167 ms 117076 KB Output is correct
11 Correct 174 ms 116160 KB Output is correct
12 Correct 178 ms 123840 KB Output is correct
13 Correct 172 ms 126660 KB Output is correct
14 Correct 146 ms 101324 KB Output is correct
15 Correct 393 ms 118140 KB Output is correct
16 Correct 368 ms 115036 KB Output is correct
17 Correct 430 ms 128144 KB Output is correct
18 Correct 408 ms 125876 KB Output is correct
19 Correct 200 ms 107180 KB Output is correct
20 Correct 207 ms 114108 KB Output is correct
21 Correct 213 ms 107388 KB Output is correct
22 Correct 190 ms 112020 KB Output is correct
23 Correct 203 ms 107712 KB Output is correct
24 Correct 202 ms 107056 KB Output is correct
25 Correct 206 ms 108204 KB Output is correct
26 Correct 191 ms 106800 KB Output is correct
27 Correct 7 ms 35676 KB Output is correct
28 Correct 8 ms 35500 KB Output is correct
29 Correct 7 ms 35688 KB Output is correct
30 Correct 7 ms 35420 KB Output is correct
31 Correct 7 ms 35420 KB Output is correct
32 Correct 8 ms 35676 KB Output is correct
33 Correct 7 ms 35672 KB Output is correct
34 Correct 7 ms 35676 KB Output is correct
35 Correct 7 ms 35420 KB Output is correct
36 Correct 19 ms 43864 KB Output is correct
37 Correct 178 ms 123080 KB Output is correct
38 Correct 165 ms 119428 KB Output is correct
39 Correct 162 ms 115908 KB Output is correct
40 Correct 146 ms 110976 KB Output is correct
41 Correct 136 ms 110016 KB Output is correct
42 Correct 124 ms 106948 KB Output is correct
43 Correct 179 ms 120120 KB Output is correct
44 Correct 171 ms 121980 KB Output is correct
45 Correct 162 ms 123764 KB Output is correct
46 Correct 147 ms 115340 KB Output is correct
47 Correct 30 ms 43868 KB Output is correct
48 Correct 407 ms 121536 KB Output is correct
49 Correct 427 ms 119128 KB Output is correct
50 Correct 357 ms 117700 KB Output is correct
51 Correct 352 ms 114880 KB Output is correct
52 Correct 310 ms 109192 KB Output is correct
53 Correct 238 ms 85880 KB Output is correct
54 Correct 378 ms 120496 KB Output is correct
55 Correct 448 ms 123168 KB Output is correct
56 Correct 432 ms 126372 KB Output is correct
57 Correct 303 ms 116164 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35416 KB Output is correct
2 Correct 6 ms 35416 KB Output is correct
3 Correct 6 ms 35420 KB Output is correct
4 Correct 6 ms 35420 KB Output is correct
5 Correct 7 ms 35548 KB Output is correct
6 Correct 7 ms 35528 KB Output is correct
7 Correct 7 ms 35676 KB Output is correct
8 Correct 7 ms 35676 KB Output is correct
9 Correct 7 ms 35676 KB Output is correct
10 Correct 137 ms 102172 KB Output is correct
11 Correct 167 ms 117076 KB Output is correct
12 Correct 174 ms 116160 KB Output is correct
13 Correct 178 ms 123840 KB Output is correct
14 Correct 172 ms 126660 KB Output is correct
15 Correct 146 ms 101324 KB Output is correct
16 Correct 393 ms 118140 KB Output is correct
17 Correct 368 ms 115036 KB Output is correct
18 Correct 430 ms 128144 KB Output is correct
19 Correct 408 ms 125876 KB Output is correct
20 Correct 200 ms 107180 KB Output is correct
21 Correct 207 ms 114108 KB Output is correct
22 Correct 213 ms 107388 KB Output is correct
23 Correct 190 ms 112020 KB Output is correct
24 Correct 203 ms 107712 KB Output is correct
25 Correct 202 ms 107056 KB Output is correct
26 Correct 206 ms 108204 KB Output is correct
27 Correct 191 ms 106800 KB Output is correct
28 Correct 7 ms 35676 KB Output is correct
29 Correct 8 ms 35500 KB Output is correct
30 Correct 7 ms 35688 KB Output is correct
31 Correct 7 ms 35420 KB Output is correct
32 Correct 7 ms 35420 KB Output is correct
33 Correct 8 ms 35676 KB Output is correct
34 Correct 7 ms 35672 KB Output is correct
35 Correct 7 ms 35676 KB Output is correct
36 Correct 7 ms 35420 KB Output is correct
37 Correct 19 ms 43864 KB Output is correct
38 Correct 178 ms 123080 KB Output is correct
39 Correct 165 ms 119428 KB Output is correct
40 Correct 162 ms 115908 KB Output is correct
41 Correct 146 ms 110976 KB Output is correct
42 Correct 136 ms 110016 KB Output is correct
43 Correct 124 ms 106948 KB Output is correct
44 Correct 179 ms 120120 KB Output is correct
45 Correct 171 ms 121980 KB Output is correct
46 Correct 162 ms 123764 KB Output is correct
47 Correct 147 ms 115340 KB Output is correct
48 Correct 30 ms 43868 KB Output is correct
49 Correct 407 ms 121536 KB Output is correct
50 Correct 427 ms 119128 KB Output is correct
51 Correct 357 ms 117700 KB Output is correct
52 Correct 352 ms 114880 KB Output is correct
53 Correct 310 ms 109192 KB Output is correct
54 Correct 238 ms 85880 KB Output is correct
55 Correct 378 ms 120496 KB Output is correct
56 Correct 448 ms 123168 KB Output is correct
57 Correct 432 ms 126372 KB Output is correct
58 Correct 303 ms 116164 KB Output is correct
59 Correct 100 ms 55512 KB Output is correct
60 Correct 375 ms 117268 KB Output is correct
61 Correct 396 ms 114848 KB Output is correct
62 Correct 414 ms 124604 KB Output is correct
63 Correct 410 ms 125132 KB Output is correct
64 Correct 7 ms 35420 KB Output is correct
65 Correct 7 ms 35712 KB Output is correct
66 Correct 7 ms 35928 KB Output is correct
67 Correct 7 ms 35604 KB Output is correct
68 Correct 7 ms 35420 KB Output is correct
69 Correct 7 ms 35676 KB Output is correct
70 Correct 8 ms 35772 KB Output is correct
71 Correct 9 ms 35676 KB Output is correct
72 Correct 8 ms 35932 KB Output is correct
73 Correct 8 ms 35676 KB Output is correct
74 Correct 153 ms 108212 KB Output is correct
75 Correct 161 ms 119188 KB Output is correct
76 Correct 146 ms 114564 KB Output is correct
77 Correct 134 ms 111040 KB Output is correct
78 Correct 68 ms 55736 KB Output is correct
79 Correct 60 ms 56004 KB Output is correct
80 Correct 134 ms 92504 KB Output is correct
81 Correct 207 ms 128308 KB Output is correct
82 Correct 218 ms 127776 KB Output is correct
83 Correct 256 ms 133864 KB Output is correct
84 Correct 166 ms 127676 KB Output is correct
85 Correct 191 ms 126152 KB Output is correct
86 Correct 80 ms 63228 KB Output is correct
87 Correct 404 ms 123072 KB Output is correct
88 Correct 362 ms 122920 KB Output is correct
89 Correct 298 ms 113856 KB Output is correct
90 Correct 146 ms 58380 KB Output is correct
91 Correct 166 ms 63400 KB Output is correct
92 Correct 290 ms 95624 KB Output is correct
93 Correct 436 ms 133044 KB Output is correct
94 Correct 364 ms 129944 KB Output is correct
95 Correct 516 ms 138420 KB Output is correct
96 Correct 404 ms 127168 KB Output is correct
97 Correct 313 ms 126988 KB Output is correct