Submission #1231610

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231610		CELD_07	Swapping Cities (APIO20_swap)	C++20	0 / 100	106 ms	24104 KiB

swap

#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, res;

inline void solve(){
    vector<ll>().swap(p);
    vector<ll>().swap(s);
    vector<ll>().swap(v2);
    vector<vector<pair<ll, ll>>>().swap(adj);
    adj.resize(n+1);
    v2.assign(n+1, 0);
    p.resize(n+1);
    s.assign(n+1, 1);
    iota(all(p), 0);
    for(auto& [w, x, y]: v1){
    bool p=0;
    if(_find(x)==_find(y))p=1;
    _union(x, y, w);
    adj[x].push_back({y, w});
    adj[y].push_back({x, w});
    ll o=adj[x].size(), o1=adj[y].size();
    if(o>2 || o1>2 || p)v2[_find(x)]=1;
    }
}
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]});
}
sort(all(v1));
solve();
}
int getMinimumFuelCapacity(int X, int Y) {
    if(v2[_find(X)])return res;
  return -1;
}
/*
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;
}
}
*/

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