Submission #1057909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057909		erray	Fountain Parks (IOI21_parks)	C++17	100 / 100	397 ms	37708 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG 
  #include "/home/hp/contests/debug.h"
#else 
  #define debug(...) void(37)
#endif

struct DSU {
  vector<int> link;
  DSU(int n) {
    link.resize(n);
    iota(link.begin(), link.end(), 0);
  }
  int get(int v) {
    return link[v] = (link[v] == v ? v : get(link[v]));
  }
  bool unite(int x, int y) {
    x = get(x), y = get(y);
    if (x == y) return false;
    link[y] = x;
    return true;
  }
};

int construct_roads(std::vector<int> X, std::vector<int> Y) {
  debug(X, Y);
  int N = int(X.size()); 
  map<array<int, 2>, int> id;
  for (int i = 0; i < N; ++i) {
    id[{X[i], Y[i]}] = i;
  }
  auto Get = [&](int x, int y) {
    if (id.count({x, y}) == 0) return -1;
    return id[{x, y}];
  };
  vector<array<int, 2>> positions;
  constexpr int dx[] = {-1, -1, +1, +1}, dy[] = {-1, +1, +1, -1};
  for (int i = 0; i < N; ++i) {
    for (int d = 0; d < 4; ++d) {
      positions.push_back({X[i] + dx[d], Y[i] + dy[d]});
    }
  }
  DSU comp(N);
  sort(positions.begin(), positions.end());
  positions.erase(unique(positions.begin(), positions.end()), positions.end());
  vector<int> U, V, A, B;
  for (auto[x, y] : positions) {
    int parity = (x + y) / 2 % 2;
    vector<int> take;
    if (parity) {
      take = {0, 2};
    } else {
      take = {1, 3};
    }
    debug(x, y, take);
    for (auto t : take) {
      int f = Get(x + dx[t], y + dy[t]);
      int s = Get(x + dx[(t + 1) % 4], y + dy[(t + 1) % 4]);
      debug(s, f);
      if (min(f, s) > -1 && comp.unite(f, s)) {
        U.push_back(f);
        V.push_back(s);
        A.push_back(x);
        B.push_back(y);
        break;
      }
    }
  }
  bool good = true;
  for (int i = 0; i < N; ++i) {
    good &= comp.get(i) == comp.get(0);
  }
  if (good) {
    build(U, V, A, B);
    return 1;
  } else {
    return 0;
  }
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30