Submission #1047760

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047760		CISM	Fountain Parks (IOI21_parks)	C++17	45 / 100	277 ms	46760 KiB

parks

#include "parks.h"

#include <bits/stdc++.h>
using namespace std;

constexpr int kDirX[] = {0, 2, 0, -2};
constexpr int kDirY[] = {2, 0, -2, 0};

int construct_roads(std::vector<int> X, std::vector<int> Y) {
  int N = X.size();

  map<pair<int, int>, int> pos;
  for (int i = 0; i < N; ++i) {
    pos[make_pair(X[i], Y[i])] = i;
  }

  vector<bool> visited(N, false);
  vector<int> U, V, A, B;

  function<void (int)> dfs = [&] (int u) {
    for (int dir = 0; dir < 4; ++dir) {
      if (pos.count(make_pair(X[u] + kDirX[dir], Y[u] + kDirY[dir]))) {
        int v = pos[make_pair(X[u] + kDirX[dir], Y[u] + kDirY[dir])];
        if (!visited[v]) {
          U.push_back(u);
          V.push_back(v);

          //    |
          //  ^ |->
          //  | |
          // ---0---
          //    | |
          //  <-| v
          //    |
          bool odd = (X[u] + Y[u]) & 2;

          if (X[u] == X[v]) {
            B.push_back(Y[u] + (Y[u] < Y[v] ? 1 : -1));
            A.push_back(X[u] + (odd ^ (Y[u] < Y[v]) ? 1 : -1));
          } else {
            A.push_back(X[u] + (X[u] < X[v] ? 1 : -1));
            B.push_back(Y[u] + (odd ^ (X[u] < X[v]) ? -1 : 1));
          }
          visited[v] = true;
          dfs(v);
        }
      }
    }
  };

  visited[0] = true;
  dfs(0);

  if (all_of(visited.begin(), visited.end(), [](bool b) { return b; })) {
    build(U, V, A, B);
    return 1;  
  }
  return 0;
}

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