# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1231605 | CELD_07 | Swapping Cities (APIO20_swap) | C++20 | 0 ms | 0 KiB |
#include "swap.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
typedef long long ll;
typedef long double ld;
#define endl "\n"
#define vll vector<ll>
#define sd second
#define ft first
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define pll pair<ll, ll>
#define mod 1000000007
#define _set tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update>
#define inf (ll)1e15
#define db(x) //cout<<#x<<" : "<<x<<endl;
#define PRESICION(x) cout.setf(ios::fixed,ios::floatfield); cout.precision(x);
using namespace std;
using namespace __gnu_pbds;
ll dx[]={1, -1, 0, 0};
ll dy[]={0, 0, 1, -1};
inline ll sm(ll a, ll b){
return ((a%mod)+(b%mod))%mod;
}
inline ll ml(ll a, ll b){
return ((a%mod)*(b%mod))%mod;
}
inline ll rs(ll a, ll b){
return ((a%mod)-(b%mod)+mod)%mod;
}
ll bpow(ll a , ll b) {
if (b==0)return 1;
if (b%2!=0)return ((bpow(a, b-1)%mod)*(a%mod))%mod;
ll r=bpow (a ,b/ 2) ;
return ((r%mod)*(r%mod))%mod;
}
vector<vector<pair<ll, ll>>> adj, adj1;
vector<ll> s, p, v2;
vector<tuple<ll, ll, ll>> v1;
inline ll _find(ll n){
if(p[n]!=n){p[n]=_find(p[n]);return p[n];}
return n;
}
inline void _union(ll a, ll b, ll w){
a=_find(a);
b=_find(b);
if(a==b)return;
if(s[a]<s[b])swap(a, b);
s[a]+=s[b];
v2[a]|=v2[b];
p[b]=a;
}
ll n;
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
vector<vector<pair<ll, ll>>>().swap(adj);
vector<vector<pair<ll, ll>>>().swap(adj1);
n=N;
adj.resize(N+1);
adj1.resize(N+1);
res=0;
vector<tuple<ll, ll, ll>>().swap(v1);
for(int i=0; i<M; i++){
adj1[V[i]].push_back({U[i], W[i]});
adj1[U[i]].push_back({V[i], W[i]});
res+=W[i];
v1.push_back({W[i], V[i], U[i]});
}
for(int i=0; i<N; i++)if(adj1[i].size()==1)res=LLONG_MAX
sort(all(v1));
}
int getMinimumFuelCapacity(int X, int Y) {
return (res==LLONG_MAX ? -1 : res);
}
/*
int main(){
ll a, b, c;
cin>>a>>b;
vector<int> v(b), v1(b), v2(b);
for(int i=0; i<b; i++){
cin>>v[i]>>v1[i]>>v2[i];
}
init(a, b, v, v1, v2);
while(1){
cin>>a>>b;
cout<<getMinimumFuelCapacity(a, b)<<endl;
}
}
*/