Submission #897676

#	Time	Username	Problem	Language	Result	Execution time	Memory
897676		cadmiumsky	Security Guard (JOI23_guard)	C++17	50 / 100	310 ms	50676 KiB

guard

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int nmax = 2e5 + 5;

vector<int> S;

vector<int> g[nmax];

int occ[nmax];

namespace DSU {
  vector<pii> ntedg;
  int dsu[nmax];
  
  void init(int n) {
    for(int i = 0; i < n; i++)
      dsu[i] = i;
  }
  
  int f(int x) { return dsu[x] == x? x : dsu[x] = f(dsu[x]); }
  
  void unite(int x, int y) {
    pii F = pii{x, y};
    x = f(x);
    y = f(y);
    if(x == y) return;
    ntedg.emplace_back(F);
    
    dsu[x] = y;
  }
  
}

signed main() {
  cin.tie(0) -> sync_with_stdio(0);
  int n, m, q;
  cin >> n >> m >> q;
  
  S.resize(n);
  
  for(auto &x : S) cin >> x;
  
  vector<int> dir_ord(n), reidx(n + 1);
  
  iota(all(dir_ord), 0);
  sort(all(dir_ord), [&](int a, int b) { return S[a] < S[b]; });
  sort(all(S));
  
  for(int i = 0; i < n; i++)
    reidx[dir_ord[i] + 1] = i;

  //for(auto x : reidx) cerr << x << ' '; cerr << '\n';

  vector<tii> edg;
  for(int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    g[reidx[a]].emplace_back(reidx[b]);
    g[reidx[b]].emplace_back(reidx[a]);
  
    edg.emplace_back(S[reidx[a]] + S[reidx[b]], reidx[a], reidx[b]);
  }
  
  sort(all(edg));
  
  DSU::init(n);
  for(auto [C, x, y] : edg)
    DSU::unite(x, y);
  
  vector<pii> ntedg = move(DSU::ntedg);
  
  ll sum = 0;
  for(auto [a, b] : ntedg)
    sum += S[a] + S[b];
  
  cout << sum - accumulate(all(S), 0LL) + (*max_element(all(S))) << '\n';
  
}

/**
  Anul asta nu se da centroid
  -- Rugaciunile mele
*/

• Subtask 1: 12 / 12
• Subtask 2: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 13 / 13
• Subtask 5: 0 / 8
• Subtask 6: 0 / 18
• Subtask 7: 0 / 24