Submission #897753

#	Time	Username	Problem	Language	Result	Execution time	Memory
897753		cadmiumsky	Security Guard (JOI23_guard)	C++17	100 / 100	1422 ms	290740 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];

tii subtr(tii a, int b) {
  auto [u, v, w] = a;
  return tii{u - b, v, w};
}

namespace DSU {
  int dsu[nmax], mn[nmax];
  
  int newnodecnt = 0;
  
  ll sum;
  
  ll mnsum = 0;
  
  vector<int> R;
  
  multiset<tii> overall;
  
  multiset<tii> edgs[nmax];
  
  void init(int n) {
    sum = 0;
    newnodecnt = n;
    for(int i = 0; i < n; i++) {
      mnsum += S[0] + S[i],
      dsu[i] = i, mn[i] = S[i];
      for(auto x : g[i])
          edgs[i].emplace(S[x] + S[i], i, x);
      overall.emplace(subtr(*edgs[i].begin(), S[i]));
    }
    
    mnsum -= S[0] * 2;
    
    R.emplace_back(sum + mnsum);
  }
  
  int f(int x) { return dsu[x] == x? x : dsu[x] = f(dsu[x]); }
  
  void unite(int x, int y, int Cost) {
    pii F = pii{x, y};
    x = f(x);
    y = f(y);
    if(x == y) assert(false);
    
    sum += S[F.first] + S[F.second];
    mnsum -= S[0] + max(mn[x], mn[y]);
    R.emplace_back(sum + mnsum);
    
    if(sz(edgs[x]) < sz(edgs[y])) swap(x, y);
    
    if(sz(edgs[x])) overall.erase(subtr(*edgs[x].begin(), mn[x]));
    if(sz(edgs[y])) overall.erase(subtr(*edgs[y].begin(), mn[y]));
    
    dsu[y] = x;
    mn[x] = min(mn[x], mn[y]);
    for(auto [C, a, b] : edgs[y])
      edgs[x].emplace(C, a, b);
    
    while(sz(edgs[x]) > 0 && f(get<1>(*edgs[x].begin())) == f(get<2>(*edgs[x].begin()))) edgs[x].erase(edgs[x].begin());
    
    if(sz(edgs[x]))
      overall.emplace(subtr(*edgs[x].begin(), mn[x]));
  }
  
  void generate() {
    while(!overall.empty()) { 
      auto [a, b, c] = *overall.begin();
      unite(b, c, a);
    }
    return;
  }
}

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;
    
    a = reidx[a];
    b = reidx[b];
    
    g[a].emplace_back(b);
    g[b].emplace_back(a);
  }
  
  DSU::init(n);
  DSU::generate();
  
  vector<int> R = move(DSU::R);
  
  reverse(all(R));
  R.resize(q + 1, R.back());
  
  ll delta =  - accumulate(all(S), 0LL) + (*max_element(all(S)));
  for(auto x : R)
    cout << x + delta << '\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: 8 / 8
• Subtask 6: 18 / 18
• Subtask 7: 24 / 24