Submission #465882

#	Time	Username	Problem	Language	Result	Execution time	Memory
465882		alexxela12345	Fountain Parks (IOI21_parks)	C++17	100 / 100	1632 ms	68636 KiB

parks

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

using namespace std;

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

void dfs(int v) {
  used[v] = 1;
  for (int u : g[v]) {
    if (!used[u]) {
      dfs(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;
  auto add = [&](int i, int j) {
    if (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;
    pp = {x[i] + 2, y[i]};
    if (byc.count(pp)) {
      add(i, byc[pp]);
    }
    pp = {x[i], y[i] + 2};
    if (byc.count(pp)) {
      add(i, byc[pp]);
    }
    pp = {x[i] - 2, y[i]};
    if (byc.count(pp)) {
      add(i, byc[pp]);
    }
    pp = {x[i], y[i] - 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);
      }
    }
  }
  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