Submission #465828

#	Time	Username	Problem	Language	Result	Execution time	Memory
465828		alexxela12345	Fountain Parks (IOI21_parks)	C++17	5 / 100	3100 ms	120600 KiB

parks

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

using namespace std;

mt19937 rd(179);

int randint(int l, int r) {
  int b = r - l + 1;
  if (b <= 0) {
    exit(228);
  }
  int a = rd() % b + b;
  a %= b;
  return a + l;
}

vector<int> pa, ra;

int get(int v) {
  if (pa[v] == v)
    return v;
  return pa[v] = get(pa[v]);
}
void merge(int a, int b) {
  a = get(a);
  b = get(b);
  assert(a != b);
  if (ra[b] > ra[a])
    swap(a, b);
  pa[b] = a;
  if (ra[a] == ra[b])
    ra[a]++;
}

vector<vector<int>> g;
vector<int> used;

void dfs(int v) {
  used[v] = 1;
  deque<int> q;
  q.push_back(v);
  while (!q.empty()) {
    int v = q.front();
    q.pop_front();
    for (int u : g[v]) {
      if (!used[u]) {
        used[u] = 1;
        q.push_back(u);
      }
    }
  }
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
  if (x.size() == 1) {
    build({}, {}, {}, {});
    return 1;
  }
  map<pair<int, int>, int> byc;
  int n = x.size();
  for (int i = 0; i < n; i++) {
    byc[{x[i], y[i]}] = i;
  }
  g.clear();
  g.resize(n);
  map<pair<int, int>, int> cnt;
  pa.assign(n, 0);
  ra.assign(n, 0);
  iota(pa.begin(), pa.end(), 0);
  set<pair<int, int>> alive;

  auto add = [&](int i, int j) {
    if (i < j) {
      alive.insert({i, j});
      g[i].push_back(j);
      g[j].push_back(i);
      if (x[i] == x[j]) {
        cnt[{x[i] + 1, (y[i] + y[j]) / 2}] += 1;
        cnt[{x[i] - 1, (y[i] + y[j]) / 2}] += 1;
      } else {
        cnt[{(x[i] + x[j]) / 2, y[i] + 1}] += 1;
        cnt[{(x[i] + x[j]) / 2, y[i] - 1}] += 1;
      }
    }
  };
  for (int i = 0; i < n; i++) {
    {
      pair<int, int> pp = {x[i], y[i]};
      pp.first += 2;
      if (byc.count(pp)) {
        add(i, byc[pp]);
      }
    }
    {
      pair<int, int> pp = {x[i], y[i]};
      pp.second += 2;
      if (byc.count(pp)) {
        add(i, byc[pp]);
      }
    }
    {
      pair<int, int> pp = {x[i], y[i]};
      pp.first -= 2;
      if (byc.count(pp)) {
        add(i, byc[pp]);
      }
    }
    {
      pair<int, int> pp = {x[i], y[i]};
      pp.second -= 2;
      if (byc.count(pp)) {
        add(i, byc[pp]);
      }
    }
  }
  used.assign(n, 0);
  dfs(0);
  if (*min_element(used.begin(), used.end()) == 0) {
    return 0;
  }
  set<pair<int, int>> ones;
  for (auto &el : cnt) {
    if (el.second == 1) {
      ones.insert(el.first);
    }
  }
  vector<int> u, v, a, b;

  g.clear();
  g.resize(n);

  auto chk = [&](pair<int, int> pp) {
    cnt[pp] -= 1;
    switch (cnt[pp]) {
    case 1: {
      ones.insert(pp);
    };
    case 0: {
      ones.erase(pp);
    };
    }
  };

  auto die = [&](int i, int j) {
    if (j < i)
      swap(i, j);
    alive.erase({i, j});
    if (x[i] == x[j]) {
      pair<int, int> pp;
      pp = {x[i] + 1, (y[i] + y[j]) / 2};
      chk(pp);
      pp = {x[i] - 1, (y[i] + y[j]) / 2};
      chk(pp);
    } else {
      pair<int, int> pp;
      pp = {(x[i] + x[j]) / 2, y[i] + 1};
      chk(pp);
      pp = {(x[i] + x[j]) / 2, y[i] - 1};
      chk(pp);
    }
  };
  auto al = [&](int i, int j) {
    if (j < i)
      swap(i, j);
    return alive.count({i, j});
  };
  auto check_edge = [&](int i, int j, pair<int, int> xy) {
    if (al(i, j) && get(i) != get(j)) {
      u.push_back(i);
      v.push_back(j);
      merge(i, j);
      a.push_back(xy.first);
      b.push_back(xy.second);
      die(i, j);
    } else if (al(i, j)) {
      die(i, j);
    }
  };

  while (true) {
    while (!ones.empty()) {
      pair<int, int> xy = *ones.begin();
      ones.erase(ones.begin());
      pair<int, int> RU, RD, LD, LU;
      RU = RD = LD = LU = xy;
      RU.first++, RU.second++;
      RD.first++, RD.second--;
      LU.first--, LU.second++;
      LD.first--, LD.second--;
      size_t was = u.size();
      if (byc.count(RU) && byc.count(RD)) {
        int i = byc[RU];
        int j = byc[RD];
        check_edge(i, j, xy);
      }
      if (byc.count(RD) && byc.count(LD)) {
        int i = byc[RD];
        int j = byc[LD];
        check_edge(i, j, xy);
      }
      if (byc.count(LD) && byc.count(LU)) {
        int i = byc[LD];
        int j = byc[LU];
        check_edge(i, j, xy);
      }
      if (byc.count(LU) && byc.count(RU)) {
        int i = byc[LU];
        int j = byc[RU];
        check_edge(i, j, xy);
      }
      if (u.size() != was) {
        cnt[xy] = -100;
      }
      assert(u.size() - was <= 1);
    }
    auto alive2 = alive;
    vector<pair<int, int>> kek;
    for (auto [i, j] : alive2) {
      if (get(i) == get(j)) {
        die(i, j);
      } else {
        kek.push_back({i, j});
      }
    }
    assert(kek.size() == alive.size());
    if (ones.empty()) {
      if (alive.empty() || clock() > 3 * CLOCKS_PER_SEC)
	break;
      int ind = randint(0, kek.size() - 1);
      auto [i, j] = kek[ind];
      vector<pair<int, int>> can;
      pair<int, int> pp;
      if (x[i] == x[j]) {
	pp = {x[i] + 1, (y[i] + y[j]) / 2};
	if (cnt[pp] >= 0) {
	  can.push_back(pp);
	}
	pp = {x[i] - 1, (y[i] + y[j]) / 2};
	if (cnt[pp] >= 0) {
	  can.push_back(pp);
	}
      } else {
	pp = {(x[i] + x[j]) / 2, y[i] + 1};
	if (cnt[pp] >= 0) {
	  can.push_back(pp);
	}
	pp = {(x[i] + x[j]) / 2, y[i] - 1};
        if (cnt[pp] >= 0) {
          can.push_back(pp);
        }
      }
      if (can.empty()) {
        return 0;
      }
      pair<int, int> xy = can[randint(0, can.size() - 1)];
      u.push_back(i);
      v.push_back(j);
      merge(i, j);
      a.push_back(xy.first);
      b.push_back(xy.second);
      cnt[xy] = -100;
      die(i, j);
    }
  }

  for (int i = 0; i < (int)u.size(); i++) {
    g[u[i]].push_back(v[i]);
    g[v[i]].push_back(u[i]);
  }
  used.assign(n, 0);
  dfs(0);
  assert(*min_element(used.begin(), used.end()) == 1);

  build(u, v, a, b);
  return 1;
}

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