Submission #296905

#TimeUsernameProblemLanguageResultExecution timeMemory
296905ASDF123Wiring (IOI17_wiring)C++17
0 / 100
5 ms6528 KiB
#include "wiring.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
#define szof(s) (int)s.size()
#define pii pair<int, int>
#define ll long long
#define fr first
#define sc second
using namespace std;

const int N = (int)2e5 + 5;
vector <int> g[N];

struct Edge {
  int u, v, len;
  Edge(int u_, int v_, int len_) {
    u = u_, v = v_, len = len_;
  }
  Edge () {
    
  }
};

bool operator < (const Edge &a, const Edge &b) {
  return a.len < b.len;
}

int pr[N], sz[N];

int findp(int v) {
  if (pr[v] == v) {
    return v;
  }
  return pr[v] = findp(pr[v]);
}

void unite(int a, int b) {
  a = findp(a);
  b = findp(b);
  if (sz[a] > sz[b]) {
    swap(a, b);
  }
  pr[a] = b;
  sz[b] += sz[a];
}

long long min_total_length(vector<int> r, vector<int> b) {
  vector <Edge> edges;
  for (int i = 1; i < N; i++) {
    pr[i] = i, sz[i] = 1;
  }
  for (int i = 0; i < szof(r); i++) {
    for (int j = 0; j < szof(b); j++) {
      int u = i + 1;
      int v = szof(r) + j + 1;
      edges.push_back(Edge(u, v, abs(r[i] - b[j])));
    }
  }
  sort(edges.begin(), edges.end());
  ll ans = 0;
  for (Edge el : edges) {
    if (findp(el.u) != findp(el.v)) {
      unite(el.u, el.v);
      ans += el.len;
    }
  }
  return ans;
}
#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...