Submission #465880

#	Time	Username	Problem	Language	Result	Execution time	Memory
465880		alexxela12345	Fountain Parks (IOI21_parks)	C++17	100 / 100	1889 ms	75052 KiB

parks

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

using namespace std;

random_device rddev;
mt19937 rd(rddev());

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;
  }
  vector<int> u, v, a, b;

  for (auto [xy, _] : cnt) {
    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--;
    if ((xy.first + xy.second) % 4) {
      // left right
      if (byc.count(RU) && byc.count(RD)) {
	u.push_back(byc[RU]);
	v.push_back(byc[RD]);
	a.push_back(xy.first);
	b.push_back(xy.second);
      } else if (byc.count(LU) && byc.count(LD)) {
	u.push_back(byc[LU]);
	v.push_back(byc[LD]);
	a.push_back(xy.first);
	b.push_back(xy.second);
      }
    } else {
      if (byc.count(RU) && byc.count(LU)) {
	u.push_back(byc[RU]);
	v.push_back(byc[LU]);
	a.push_back(xy.first);
	b.push_back(xy.second);
      } else if (byc.count(RD) && byc.count(LD)) {
        u.push_back(byc[RD]);
        v.push_back(byc[LD]);
        a.push_back(xy.first);
        b.push_back(xy.second);
      }
    }
  }

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

  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: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30