| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 979534 | vjudge1 | 자매 도시 (APIO20_swap) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 =3e5 + 9 , mod = 1e9 + 7;
ll a[N] , b[N] , d[N] , p[N][3] , sz[N] , dp[N] , c[N] ;
vector<pair<ll , ll >>v[N];
vector<pair<ll,ll>>vv;
int get(int x , vector<pair<ll,ll>>&vv ){
if(vv.size())
vv.pb({x , p[x][1] });
return (p[x][0] == x ? x : get(p[x][0] , vv));
}
void join(int x , int y , ll k){
x = get(x , vv) , y = get(y , vv);
if(x != y){
if(sz[x] < sz[y])
swap(x , y);
p[y][0] = x;
p[y][1] = k;
p[x][2] = min(p[y][2] , p[x][2]);
sz[x] += sz[y];
}else {
p[y][2] = min(p[y][2] , k);
}
}
void init(ll n , ll m , vector<int>v , vector<int>u , vector<int>c)
{
ll i , j ,l ,r , x , y , s = 0 , f , k , mx = 0 , mn = 1e18;
vector<pair<ll,pair<ll,ll>>>vc;
for(i = 0; i <= n; i++)
p[i][0] = i , p[i][1] = 0, p[i][2] = 1e18 , sz[i] = 1;
for(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);
}
}
int getMinimumFuelCapacity(int l, int r) {
l++;
r++;
vector<pair<ll,ll>>v1 = {{0 , 0}}, v2= {{-1 , 0}};
get(l , v1);
get(r , v2);
ll x = v1.size() - 1, y = v2.size() - 1;
ll mx = 0 , mn = 1e18;
while(1){
mn = min({mn , max(v1[x].se , p[v1[x].fi][2] )});
if(v1[x].fi != v2[y].fi){
mx = max({mx , v1[x].se , v2[y].se });
break;
}
x-- , y--;
}
mx = max(mx , mn);
while(1){
if(v1[x].fi != v2[y].fi){
mx = max({mx , v1[x].se , v2[y].se });
break;
}
x-- , y--;
}
if(mx == 1e18)
mx = -1;
return mx;
return mx;
}
/*
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";
}*/