제출 #1201382

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1201382		Rasoul006	Swapping Cities (APIO20_swap)	C++20	0 / 100	2095 ms	589824 KiB

swap

#include "swap.h"

#include <bits/stdc++.h>

#define endl "\n"

#define F first

#define S second

#define pb push_back

#define all(x) x.begin() , x.end()

#define mm(dp , val) memset (dp , val , sizeof dp)

#define mid ((r+l)>>1)

#define lx (n<<1)

#define rx ((n<<1)|1)

#define low (i&(-i))

#define lb lower_bound

#define ub upper_bound

#define no void (cout << "NO" << endl)

#define one void (cout << "-1" << endl)

#define zer void (cout << "0" << endl)

#define yes void (cout << "YES" << endl)

typedef long long ll;

using namespace std;

const int logn = 26 ;

const int N = 1e5+5;

const int mod = 1e9+7;

const long long oo = 4557430888798830399 ;

ll dx[] = {0 , 0 , 1 , -1};
ll dy[] = {1 , -1 , 0 , 0};

ll t , n , m , a[N] , lvl[N] , dp[N][logn] , s[N][logn] , mn[N][logn] ;

vector <pair<ll,ll>> v[N] ;

void dfs (ll u , ll p , ll cst)
{
    lvl[u] = lvl[p]+1 ; dp[u][0] = p ; s[u][0] = cst ;

    for (auto it : v[p]) if (it.F != u && it.F != dp[p][0]) mn[u][0] = min(mn[u][0] , it.S) ;

    for (auto it : v[u]) if (it.F != p)  dfs(it.F , u , it.S);

}

void init(int n , int m , vector<int> x , vector<int> y , vector<int> w)
{
    for (int i = 0 ; i < m ; i++)
        v[x[i]].pb({y[i],w[i]}) , v[y[i]].pb({x[i],w[i]}) ;

    for (int i = 0 ; i <= n ; i++)
        for (int j = 0 ; j < logn ; j++)
            mn[i][j] = oo , s[i][j] = 0 , dp[i][j] = 0 ;

    dfs (0 , 0 , 0) ;

    for (int i = 1 ; i < logn ; i++)
    {
        for (int u = 0 ; u < n ; u++)
        {
            dp[u][i] = dp[dp[u][i-1]][i-1] ;
            s[u][i] = s[u][i-1] + s[dp[u][i-1]][i-1] ;
            mn[u][i] = min(mn[u][i-1] , mn[dp[u][i-1]][i-1]) ;
        }
    }
}

int getMinimumFuelCapacity(int x , int y)
{
    ll mni = oo , ans = 0 , a = x , b = y ;

    if (lvl[a] > lvl[b]) swap(a , b) , swap(x , y);

    ll dif = lvl[b] - lvl[a] ;
    for (int i = logn ; i >= 0 ; i--)
    {
        if ((1ll << i) & dif)
        {
            ans += s[b][i] ;
            mni = min(mni , mn[b][i]) ;
            b = dp[b][i] ;
        }
    }

    for (auto it : v[y]) if (it.F != dp[y][0]) mni = min (mni , it.S) ;

    for (int i = logn-1 ; i >= 0 ; i--)
    {
        if (dp[a][i] == dp[b][i]) continue ;

        ans += s[a][i] + s[b][i] ;
        mni = min({mni , mn[a][i] , mn[b][i]}) ;
        a = dp[a][i] , b = dp[b][i] ;
    }

    if (a != b)
    {
        for (auto it : v[x]) if (it.F != dp[x][0]) mni = min (mni , it.S) ;
        ans += s[a][0] + s[b][0] ;
        ll lca = dp[a][0] ;
        for (auto it : v[lca])
            if (it.F != a && it.F != b) mni = min(mni , it.S) ;
    }
    else mni = min(mni , s[a][0] + oo*(!a)) ;

    return (mni == oo ? -1 : 2*(ans + mni)) ;
}

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