제출 #1231610

#제출 시각아이디문제언어결과실행 시간메모리
1231610CELD_07Swapping Cities (APIO20_swap)C++20
0 / 100
106 ms24104 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, 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; } } */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...