Submission #847153

#TimeUsernameProblemLanguageResultExecution timeMemory
847153errorgornSecurity Guard (JOI23_guard)C++17
37 / 100
197 ms42148 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define ll long long #define ii pair<int,int> #define iii tuple<int,int,int> #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]; set<ii> al[200005]; 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]; int ans=0; rep(x,0,m){ int a,b; cin>>a>>b; if (ii(arr[a],a)>ii(arr[b],b)) swap(a,b); al[a].insert({arr[b],b}); ans+=arr[a]; } 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); }); idx.pob(); for (auto u:idx){ int v=(*al[u].begin()).se; ans+=arr[v]-arr[u]; al[u].erase(al[u].begin()); if (sz(al[u])>sz(al[v])) swap(al[u],al[v]); for (auto it:al[u]) al[v].insert(it); } 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...