| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 387701 | RohamIzadidoost | Swapping Cities (APIO20_swap) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("Ofast,unroll-loops,fast-math")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define pll pair<ll , ll >
#define all(x) (x).begin(),(x).end()
#define SZ(x) (ll)(x).size()
#define X first
#define Y second
#define mp make_pair
#define pii pair<int , int>
#define vec vector
#define file_io freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
// BIG p : 1000000000000037 , 100000000003
ll poww(ll a, ll b, ll md) {
return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}
const int maxn = 2000*100+5 ;
const ll inf = 9223372036854775807 ;
const ll mod = 1e9 + 7 ;
const int lg = 20 ;
int par[maxn] , sz[maxn] , mark[maxn] , d[maxn] , flag , ans ;
vec<pair<int , pii>> e ;
void prep(){
for(int i = 0 ; i < maxn ; i ++ ){
par[i] = i ;
sz[i] = 1 ;
mark[i] = d[i] = 0 ;
}
}
int getpar(int v){
return v == par[v] ? v : par[v] = getpar(par[v]) ;
}
void merge(int x , int y){
d[x] ++ , d[y] ++ ;
flag = 0 ; if(d[x] >= 3 || d[y] >= 3) flag = 1 ;
x = getpar(x) , y = getpar(y) ;
if(x == y){
mark[x] = 1 ;
return ;
}
if(sz[x] < sz[y]) swap(x , y) ;
par[y] = x ;
sz[x] += sz[y] ;
mark[x] |= flag ;
}
int getMinimumFuelCapacity(int x , int y){
prep() ;
for(auto u : e){
merge(u.Y.X , u.Y.Y) ;
ans = u.X ;
if(getpar(x) == getpar(y) && mark[getpar(x)]){
return ans ;
}
}
return -1 ;
}
void init(int n , int m , int A[] , int B[] , int W[]){
for(int i = 0 ; i < m ; i ++ ){
e.pb({W[i] , {A[i] , B[i]}}) ;
}
sort(all(e)) ;
}
/*int main()
{
migmig ;
int n , m ;
cin>>n>>m ;
int u[m] , v[m] , w[m] ;
for(int i = 0 ; i < m ; i ++ ) cin>>u[i]>>v[i]>>w[i] ;
init(n , m , u , v , w) ;
int q ;
cin>>q ;
while(q--){
int U , V ;
cin>>U>>V ;
cout<<getMinimumFuelCapacity(U , V) << endl ;
}
}*/