oj.uz

Submission #980005

# Submission time Handle Problem Language Result Execution time Memory
980005 2024-05-11T19:10:55 Z hasan2006 Swapping Cities (APIO20_swap) C++17
7 / 100
 230 ms 102296 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];
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];
        v[min(X , Y)].pb({k , max(X , Y)});
    }else {
        v1[X].pb({k , Y});
        v1[Y].pb({k , X});
    }
}
ll timer = 0;
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;
    }
    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 = 20; 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);
    if(ans == 1e18)
        ans = -1;
    return ans;
}
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 = 20; 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 = 20; 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);
    ans = max(ans , mn);
    if(ans == 1e18)
        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);
   for(int i = 1; i <= n ; i++)
        sort(all(::v[i])) , sort(rall(::v1[i]));
    dfs(1);
    dfs1(1);
}


int getMinimumFuelCapacity(int l, int r) {
        l++ , r++;
        return lca(l , r);
}
/*
int main(){
    init(5, 6, {0, 0, 1, 1, 1, 2}, {1, 2, 2, 3, 4, 3}, {4, 4, 1, 2, 10, 3});
    cout<<getMinimumFuelCapacity(1,2)<<"\n";
    cout<<getMinimumFuelCapacity(2,4)<<"\n";
    cout<<getMinimumFuelCapacity(0,1)<<"\n";
}*/

Compilation message

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

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29272 KB Output is correct
2 Correct 6 ms 29276 KB Output is correct
3 Correct 5 ms 29276 KB Output is correct
4 Incorrect 5 ms 29364 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29272 KB Output is correct
2 Correct 6 ms 29276 KB Output is correct
3 Correct 201 ms 100984 KB Output is correct
4 Correct 200 ms 102296 KB Output is correct
5 Correct 230 ms 101320 KB Output is correct
6 Correct 194 ms 101564 KB Output is correct
7 Correct 188 ms 101576 KB Output is correct
8 Correct 188 ms 101056 KB Output is correct
9 Correct 184 ms 101824 KB Output is correct
10 Correct 196 ms 100796 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29272 KB Output is correct
2 Correct 6 ms 29276 KB Output is correct
3 Correct 5 ms 29276 KB Output is correct
4 Incorrect 5 ms 29364 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29272 KB Output is correct
2 Correct 6 ms 29276 KB Output is correct
3 Correct 5 ms 29276 KB Output is correct
4 Incorrect 5 ms 29364 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29272 KB Output is correct
2 Correct 6 ms 29276 KB Output is correct
3 Correct 5 ms 29276 KB Output is correct
4 Incorrect 5 ms 29364 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29272 KB Output is correct
2 Correct 6 ms 29276 KB Output is correct
3 Correct 5 ms 29276 KB Output is correct
4 Incorrect 5 ms 29364 KB Output isn't correct
5 Halted 0 ms 0 KB -