Submission #387707

#	Time	Username	Problem	Language	Result	Execution time	Memory
387707		RohamIzadidoost	Swapping Cities (APIO20_swap)	C++14	37 / 100	2075 ms	12172 KiB

swap

#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 | mark[y] ) ; 
}
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 , vec<int> A , vec<int> B , vec<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 ; 
	}
}*/

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