Submission #436383

#	Time	Username	Problem	Language	Result	Execution time	Memory
436383		VEGAnn	Fountain Parks (IOI21_parks)	C++17	100 / 100	556 ms	41632 KiB

parks

#include "parks.h"

#include <algorithm>
#include <queue>
#include <vector>

const int kMax = 200005;

std::vector<std::pair<int, int>> fountains[kMax];

bool isConnected(std::vector<std::vector<int>> adj) {
  int n = adj.size();
  std::vector<bool> vis(n);
  std::queue<int> q;
  q.push(0); vis[0] = true;

  while (!q.empty()) {
    int u = q.front();
    q.pop();

    for (int v : adj[u]) {
      if (vis[v]) continue;
      vis[v] = true;
      q.push(v);
    }
  }

  return all_of(vis.begin(), vis.end(), [](bool visited) { return visited; });
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
  int n = x.size();
  for (int i = 0; i < n; ++i) {
    fountains[x[i]].emplace_back(y[i], i);
  }
  for (int i = 0; i < kMax; ++i) {
    std::sort(fountains[i].begin(), fountains[i].end());
  }
  
  std::vector<std::tuple<int, int, int, int, int>> pathways;
  std::vector<std::vector<int>> adj(n);
  for (int i = 0; i < n; ++i) {
    auto it = std::lower_bound(fountains[x[i] + 2].begin(), fountains[x[i] + 2].end(),
                               std::make_pair(y[i], -1));
    if (it != fountains[x[i] + 2].end() && it->first == y[i]) {
      int ny = x[i] + y[i] & 2 ? y[i] + 1 : y[i] - 1;
      pathways.emplace_back(x[i] + 1, ny, x[i] + y[i], i, it->second);
      adj[i].emplace_back(it->second);
      adj[it->second].emplace_back(i);
    }
    it = std::lower_bound(fountains[x[i]].begin(), fountains[x[i]].end(),
                          std::make_pair(y[i] + 2, -1));
    if (it != fountains[x[i]].end() && it->first == y[i] + 2) {
      int nx = x[i] + y[i] & 2 ? x[i] - 1 : x[i] + 1;
      pathways.emplace_back(nx, y[i] + 1, x[i] + y[i], i, it->second);
      adj[i].emplace_back(it->second);
      adj[it->second].emplace_back(i);
    }
  }

  if (!isConnected(adj)) return 0;

  std::sort(pathways.begin(), pathways.end());

  std::vector<int> u, v, a, b;
  for (int i = 0; i < static_cast<int>(pathways.size()); ++i) {
    if (i > 0 && std::get<0>(pathways[i]) == std::get<0>(pathways[i - 1]) &&
        std::get<1>(pathways[i]) == std::get<1>(pathways[i - 1])) {
      continue;
    }
    
    u.emplace_back(std::get<3>(pathways[i]));
    v.emplace_back(std::get<4>(pathways[i]));
    a.emplace_back(std::get<0>(pathways[i]));
    b.emplace_back(std::get<1>(pathways[i]));
  }

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

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:46:21: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   46 |       int ny = x[i] + y[i] & 2 ? y[i] + 1 : y[i] - 1;
parks.cpp:54:21: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   54 |       int nx = x[i] + y[i] & 2 ? x[i] - 1 : x[i] + 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