Submission #296905

#	Time	Username	Problem	Language	Result	Execution time	Memory
296905		ASDF123	Wiring (IOI17_wiring)	C++17	0 / 100	5 ms	6528 KiB

wiring

#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;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45