Submission #979771

#	Time	Username	Problem	Language	Result	Execution time	Memory
979771		vjudge1	자매 도시 (APIO20_swap)	C++17	0 / 100	4 ms	25176 KiB

swap

#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] , c[N][25] , d[N] , par[N][25] , mx[N][25] , us[N] , us1[N];
vector<pair<ll,ll>>v[N] , v1[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 = 0){
    a[n] = k;
    if(n == 1)
    a[n] = 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;
}

bool ok(int u, int v)
{

    return (u && us[u] <= us[v] && us1[u] >= us1[v]);
}

ll get(int x , int y){
    ll mn = 1e18 , ans = 0;
    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 , dp[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];
            }
    }
    mn = min(mn, a[par[x][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 ,1ll * 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);
}


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

Compilation message (stderr)

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

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27