제출 #854283

#제출 시각아이디문제언어결과실행 시간메모리
854283errorgornSecurity Guard (JOI23_guard)C++17
37 / 100
124 ms21344 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define ll long long #define ii pair<ll,ll> #define iii pair<ii,ll> #define fi first #define se second #define endl '\n' #define debug(x) cout << #x << ": " << x << endl #define pub push_back #define pob pop_back #define puf push_front #define pof pop_front #define lb lower_bound #define ub upper_bound #define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) #define all(x) (x).begin(),(x).end() #define sz(x) (int)(x).size() mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); int n,m,k; int arr[200005]; vector<int> al[200005]; int p[200005]; int par(int i){ if (p[i]==i) return p[i]; else return p[i]=par(p[i]); } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin.exceptions(ios::badbit | ios::failbit); cin>>n>>m>>k; rep(x,1,n+1) cin>>arr[x]; rep(x,0,m){ int a,b; cin>>a>>b; if (ii(arr[a],a)<ii(arr[b],b)) swap(a,b); al[a].pub(b); } vector<int> idx; rep(x,1,n+1) idx.pub(x); sort(all(idx),[](int i,int j){ return ii(arr[i],i)<ii(arr[j],j); }); rep(x,1,n+1) sort(all(al[x]),[](int i,int j){ return arr[i]<arr[j]; }); rep(x,1,n+1) p[x]=x; int ans=0; for (auto u:idx){ for (auto v:al[u]) if (par(v)!=u){ ans+=arr[u]-arr[par(v)]+arr[v]; p[par(v)]=u; } } cout<<ans<<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...
#Verdict Execution timeMemoryGrader output
Fetching results...