Submission #492855

#	Time	Username	Problem	Language	Result	Execution time	Memory
492855		Sunset	Fountain Parks (IOI21_parks)	C++17	5 / 100	689 ms	71756 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
#define X first
#define Y second
#define sz(x) ((int)(x).size())

using namespace std;
typedef pair<int, int> ipair;
const ipair D[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

ipair operator + (ipair const& a, ipair const& b) { return {a.X+b.X, a.Y+b.Y}; }
ipair operator - (ipair const& a, ipair const& b) { return {a.X-b.X, a.Y-b.Y}; }
ipair operator * (ipair const& a, int b) { return {a.X*b, a.Y*b}; }

int construct_roads(std::vector<int> ix, std::vector<int> iy) {
  int n = sz(ix);
  map<ipair, int> fs;
  set<pair<ipair, ipair>> roads;
  for (int i = 0; i < n; ++i)
    fs[{ix[i], iy[i]}] = i;

  vector<int> ansA, ansB, ansX, ansY;

  set<ipair> q;
  set<ipair> vis;
  set<ipair> done;
  q.insert({ix[0], iy[0]});
  vis.insert({ix[0], iy[0]});

  bool isFirst = true;
  while (!q.empty()) {
    ipair p = *q.begin();
    q.erase(p);

    if (!isFirst) {
      for (int i = 0; i < 4; ++i) {
        ipair d = D[i];
        ipair p2 = p + d * 2;
        if (!done.count(p2)) continue;
        ipair d2;
        if ((p.X + p.Y) & 1) {
          d2 = D[(i + 1) % 4];
        } else {
          d2 = D[(i + 3) % 4];
        }
        if (roads.count({p + d2 * 2, p2 + d2 * 2})) continue;
        roads.insert({p, p2});
        roads.insert({p2, p});
        ansA.push_back(fs[p]);
        ansB.push_back(fs[p2]);
        ipair pp = p + d + d2;
        ansX.push_back(pp.X);
        ansY.push_back(pp.Y);
        break;
      }
    }
    isFirst = false;
    done.insert(p);

    for (auto d : D)
      if (fs.count(p + d * 2) && !vis.count(p + d * 2)) {
        q.insert(p + d * 2);
        vis.insert(p + d * 2);
      }
  }

  if (sz(vis) != n) return 0;
  build(ansA, ansB, ansX, ansY);
  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