Submission #1229484

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229484		rxlfd314	Fountain Parks (IOI21_parks)	C++20	30 / 100	544 ms	64788 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

struct DSU {
  vt<int> uf;
  DSU(const int n) : uf(n, -1) {}
  int find(const int i) {
    return uf[i] < 0 ? i : uf[i] = find(uf[i]);
  }
  bool unite(int a, int b) {
    if ((a = find(a)) == (b = find(b)))
      return false;
    if (uf[a] > uf[b])
      swap(a, b);
    uf[a] += uf[b];
    uf[b] = a;
    return true;
  }
};

constexpr int dir[5] = {2, 0, -2, 0, 2};

int construct_roads(vt<int> X, vt<int> Y) {
  const int N = size(X);
  map<ari2, int> points;
  vt<ari2> edges;
  FOR(i, 0, N-1) {
    FOR(j, 0, 3) {
      const int x = X[i] + dir[j];
      const int y = Y[i] + dir[j+1];
      if (points.find({x, y}) != points.end()) {
        const int k = points[{x, y}];
        edges.push_back({i, k});
      }
    }
    points[{X[i], Y[i]}] = i;
  }
  if (*max_element(all(X)) <= 6) {
    DSU uf(N);
    vt<int> A, B, C, D;
    vt<ari3> fours;
    for (const auto &[i, j] : edges) {
      if (X[i] == X[j]) {
        uf.unite(i, j);
        if (X[i] == 2) {
          A.push_back(i);
          B.push_back(j);
          C.push_back(1);
          D.push_back(Y[i] + Y[j] >> 1);
        } else if (X[i] == 6) {
          A.push_back(i);
          B.push_back(j);
          C.push_back(7);
          D.push_back(Y[i] + Y[j] >> 1);
        } else {
          fours.push_back({Y[i] + Y[j] >> 1, i, j});
        }
      }
    }
    sort(all(fours));
    int add = 1;
    set<ari2> have;
    for (const auto &[_, i, j] : fours) {
      A.push_back(i);
      B.push_back(j);
      C.push_back(4 + add);
      D.push_back(Y[i] + Y[j] >> 1);
      have.insert({4 + add, Y[i] + Y[j] >> 1});
      add *= -1;
    }
    for (const auto &[i, j] : edges) {
      if (Y[i] == Y[j]) {
        if (!uf.unite(i, j))
          continue;
        A.push_back(i);
        B.push_back(j);
        const int x = X[i] + X[j] >> 1;
        C.push_back(x);
        if (have.count({x, Y[i] + 1})) {
          assert(!have.count({x, Y[i] - 1}));
          have.insert({x, Y[i] - 1});
          D.push_back(Y[i] - 1);
        } else {
          have.insert({x, Y[i] + 1});
          D.push_back(Y[i] + 1);
        }
      }
    }
    assert(size(A) == size(B) && size(B) == size(C) && size(C) == size(D));
    if (size(A) != N - 1)
      return 0;
    build(A, B, C, D);
    return 1;
  }
  DSU uf(N);
  map<ari2, int> used;
  FOR(x, 0, size(edges) - 1) {
    auto &[i, j] = edges[x];
    if (!uf.unite(i, j))
      continue;
    used[{i, j}] = used[{j, i}] = x;
  }
  if (size(used) != 2*(N-1))
    return 0;
  vt<ari2> pairs;
  FOR(x, 0, size(edges) - 1) {
    auto &[i, j] = edges[x];
    if (used.find({i, j}) == used.end())
      continue;
    const auto calc = [&](const ari2 aa, const ari2 bb, const int p) {
      if (points.find(aa) == points.end() || points.find(bb) == points.end())
        return;
      const int a = points[aa], b = points[bb];
      if (used.find({a, p}) == used.end() || used.find({b, p}) == used.end())
        return;
      pairs.push_back({used[{a, p}], used[{b, p}]});
    };
    if (X[i] == X[j]) {
      calc({X[i] + 2, Y[i]}, {X[i] - 2, Y[i]}, i);
      calc({X[j] + 2, Y[j]}, {X[j] - 2, Y[j]}, j);
    } else {
      calc({X[i], Y[i] - 2}, {X[i], Y[i] + 2}, i);
      calc({X[j], Y[j] - 2}, {X[j], Y[j] + 2}, j);
    }
  }
  vt<int> seen(size(edges));
  vt<int> A, B, C, D;
  set<ari2> have;
  for (const auto &[ea, eb] : pairs) {
    if (seen[ea]) {
      assert(seen[eb]);
      continue;
    }
    seen[ea] = seen[eb] = 1;
    const auto &[a, b] = edges[ea];
    const auto &[c, d] = edges[eb];
    A.push_back(edges[ea][0]);
    B.push_back(edges[ea][1]);
    A.push_back(edges[eb][0]);
    B.push_back(edges[eb][1]);
    if (X[a] == X[b]) {
      assert(X[c] == X[d] && X[c] == X[a]);
      if (have.count({X[a] + 1, Y[a] + Y[b] >> 1}) || have.count({X[a] - 1, Y[c] + Y[d] >> 1})) {
        assert(!have.count({X[a] - 1, Y[a] + Y[b] >> 1}) && !have.count({X[a] + 1, Y[c] + Y[d] >> 1}));
        have.insert({X[a] - 1, Y[a] + Y[b] >> 1});
        have.insert({X[a] + 1, Y[c] + Y[d] >> 1});
        C.push_back(X[a] - 1);
        D.push_back(Y[a] + Y[b] >> 1);
        C.push_back(X[a] + 1);
        D.push_back(Y[c] + Y[d] >> 1);
      } else {
        have.insert({X[a] + 1, Y[a] + Y[b] >> 1});
        have.insert({X[a] - 1, Y[c] + Y[d] >> 1});
        C.push_back(X[a] + 1);
        D.push_back(Y[a] + Y[b] >> 1);
        C.push_back(X[a] - 1);
        D.push_back(Y[c] + Y[d] >> 1);
      }
    } else {
      assert(Y[a] == Y[b] && Y[a] == Y[c] && Y[a] == Y[d]);
      if (have.count({X[a] + X[b] >> 1, Y[a] - 1}) || have.count({X[c] + X[d] >> 1, Y[a] + 1})) {
        assert(!have.count({X[a] + X[b] >> 1, Y[a] + 1}) && !have.count({X[c] + X[d] >> 1, Y[a] - 1}));
        have.insert({X[a] + X[b] >> 1, Y[a] + 1});
        have.insert({X[c] + X[d] >> 1, Y[a] - 1});
        C.push_back(X[a] + X[b] >> 1);
        D.push_back(Y[a] + 1);
        C.push_back(X[c] + X[d] >> 1);
        D.push_back(Y[a] - 1);
      } else {
        have.insert({X[a] + X[b] >> 1, Y[a] - 1});
        have.insert({X[c] + X[d] >> 1, Y[a] + 1});
        C.push_back(X[a] + X[b] >> 1);
        D.push_back(Y[a] - 1);
        C.push_back(X[c] + X[d] >> 1);
        D.push_back(Y[a] + 1);
      }
    }
  }
  FOR(x, 0, size(edges) - 1) {
    if (seen[x])
      continue;
    const auto &[i, j] = edges[x];
    A.push_back(i);
    B.push_back(j);
    if (X[i] == X[j]) {
      if (have.count({X[i] + 1, Y[i] + Y[j] >> 1})) {
        assert(!have.count({X[i] - 1, Y[i] + Y[j] >> 1}));
        have.insert({X[i] - 1, Y[i] + Y[j] >> 1});
        C.push_back(X[i] - 1);
        D.push_back(Y[i] + Y[j] >> 1);
      } else {
        have.insert({X[i] + 1, Y[i] + Y[j] >> 1});
        C.push_back(X[i] + 1);
        D.push_back(Y[i] + Y[j] >> 1);
      }
    } else {
      if (have.count({X[i] + X[j] >> 1, Y[i] + 1})) {
        assert(!have.count({X[i] + X[j] >> 1, Y[i] - 1}));
        have.insert({X[i] + X[j] >> 1, Y[i] - 1});
        C.push_back(X[i] + X[j] >> 1);
        D.push_back(Y[i] - 1);
      } else {
        have.insert({X[i] + X[j] >> 1, Y[i] + 1});
        C.push_back(X[i] + X[j] >> 1);
        D.push_back(Y[i] + 1);
      }
    }
  }
  build(A, B, C, D);
  return 1;
}

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