oj.uz

Submission #980009

# Submission time Handle Problem Language Result Execution time Memory
980009 2024-05-11T19:13:03 Z hasan2006 Swapping Cities (APIO20_swap) C++17
0 / 100
 130 ms 97472 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 -1;
        //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 5 ms 29276 KB Output is correct
3 Correct 5 ms 29276 KB Output is correct
4 Correct 7 ms 29380 KB Output is correct
5 Correct 7 ms 29532 KB Output is correct
6 Correct 6 ms 29276 KB Output is correct
7 Correct 6 ms 29320 KB Output is correct
8 Correct 6 ms 29272 KB Output is correct
9 Correct 43 ms 53700 KB Output is correct
10 Correct 49 ms 51392 KB Output is correct
11 Correct 49 ms 57536 KB Output is correct
12 Correct 51 ms 51908 KB Output is correct
13 Correct 56 ms 52420 KB Output is correct
14 Correct 48 ms 60288 KB Output is correct
15 Correct 92 ms 49104 KB Output is correct
16 Correct 90 ms 61624 KB Output is correct
17 Correct 95 ms 68036 KB Output is correct
18 Correct 90 ms 53440 KB Output is correct
19 Incorrect 46 ms 40664 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29272 KB Output is correct
2 Correct 5 ms 29276 KB Output is correct
3 Correct 5 ms 29276 KB Output is correct
4 Correct 7 ms 29380 KB Output is correct
5 Correct 7 ms 29532 KB Output is correct
6 Correct 6 ms 29276 KB Output is correct
7 Correct 6 ms 29320 KB Output is correct
8 Correct 6 ms 29272 KB Output is correct
9 Incorrect 5 ms 29276 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 29276 KB Output isn't correct
2 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 5 ms 29276 KB Output is correct
3 Correct 5 ms 29276 KB Output is correct
4 Correct 7 ms 29380 KB Output is correct
5 Correct 7 ms 29532 KB Output is correct
6 Correct 6 ms 29276 KB Output is correct
7 Correct 6 ms 29320 KB Output is correct
8 Correct 6 ms 29272 KB Output is correct
9 Correct 43 ms 53700 KB Output is correct
10 Correct 49 ms 51392 KB Output is correct
11 Correct 49 ms 57536 KB Output is correct
12 Correct 51 ms 51908 KB Output is correct
13 Correct 56 ms 52420 KB Output is correct
14 Correct 48 ms 60288 KB Output is correct
15 Correct 92 ms 49104 KB Output is correct
16 Correct 90 ms 61624 KB Output is correct
17 Correct 95 ms 68036 KB Output is correct
18 Correct 90 ms 53440 KB Output is correct
19 Incorrect 130 ms 97472 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 29276 KB Output isn't correct
2 Halted 0 ms 0 KB -