Submission #446593

#	Time	Username	Problem	Language	Result	Execution time	Memory
446593		SuffixAutomata	Fountain Parks (IOI21_parks)	C++17	55 / 100	1254 ms	73648 KiB

parks

#include "parks.h"
 
#include <bits/stdc++.h>
using namespace std;
 
int ufs[200005];
int ge(int x) {
  if (ufs[x] == -1)
    return x;
  return ufs[x] = ge(ufs[x]);
}
 
vector<pair<int, int>> pts;
map<pair<int, int>, int> idx;
vector<pair<int, int>> elist;
int n;
 
mt19937 rng(108616);
 
vector<int> bpt[200005];
int mach[800005];
int vis[200005];
int gloti = 0;
bool dfs(int u, int ti) {
  vis[u] = ti;
  for (int v : bpt[u]) {
    if (mach[v] == -1 || ((vis[mach[v]] != ti) && dfs(mach[v], ti))) {
      mach[v] = u;
      return 1;
    }
  }
  return 0;
}
bool hasmxm(int cnt) {
  for (int i = 0; i < cnt; i++) {
    gloti++;
    if (!dfs(i, gloti))
      return 0;
  }
  return 1;
}
bool ranAttempt() {
  shuffle(elist.begin(), elist.end(), rng);
  memset(ufs, -1, sizeof ufs);
  vector<pair<int, int>> mst;
  for (auto [u, v] : elist) {
    if (ge(u) != ge(v)) {
      ufs[ge(u)] = ge(v);
      mst.push_back({u, v});
    }
  }
  if (mst.size() != n - 1)
    return 0;
  map<pair<int, int>, int> benches;
 
  int edid = 0, beid = 0;
  for (auto [u, v] : mst) {
    auto [x1, y1] = pts[u];
    auto [x2, y2] = pts[v];
    bpt[edid].clear();
    if (x1 == x2) {
      int c = min(y1, y2);
      pair<int, int> p1 = {x1 - 1, c + 1}, p2 = {x1 + 1, c + 1};
      if (!benches.count(p1))
        benches[p1] = beid++;
      if (!benches.count(p2))
        benches[p2] = beid++;
      bpt[edid].push_back(benches[p1]);
      bpt[edid].push_back(benches[p2]);
    } else {
      int c = min(x1, x2);
      pair<int, int> p1 = {c + 1, y1 + 1}, p2 = {c + 1, y1 - 1};
      if (!benches.count(p1))
        benches[p1] = beid++;
      if (!benches.count(p2))
        benches[p2] = beid++;
      bpt[edid].push_back(benches[p1]);
      bpt[edid].push_back(benches[p2]);
    }
    edid++;
  }
  for (int i = 0; i < beid; i++)
    mach[i] = -1;
  if (hasmxm(edid)) {
    vector<int> U, V;
    vector<int> mx(mst.size()), my(mst.size());
    for (auto [u, v] : mst) {
      U.push_back(u);
      V.push_back(v);
    }
    for (auto [x, i] : benches) {
      if (mach[i] == -1)
        continue;
      auto [zx, zy] = x;
      mx[mach[i]] = zx;
      my[mach[i]] = zy;
    }
    build(U, V, mx, my);
    return 1;
  }
  return 0;
}
 
int construct_roads(std::vector<int> x, std::vector<int> y) {
  if (x.size() == 1) {
    build({}, {}, {}, {});
    return 1;
  }
  n = x.size();
  pts = vector<pair<int, int>>(n);
  for (int i = 0; i < n; i++) {
    pts[i] = {x[i], y[i]};
    idx[pts[i]] = i;
  }
  for (int i = 0; i < n; i++) {
    if (idx.count({x[i] + 2, y[i]}))
      elist.push_back({i, idx[{x[i] + 2, y[i]}]});
    if (idx.count({x[i], y[i] + 2}))
      elist.push_back({i, idx[{x[i], y[i] + 2}]});
  }
  while (clock() < CLOCKS_PER_SEC) {
    if (ranAttempt())
      return 1;
  }
  return 0;
}

Compilation message (stderr)

parks.cpp: In function 'bool ranAttempt()':
parks.cpp:52:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |   if (mst.size() != n - 1)
      |       ~~~~~~~~~~~^~~~~~~~

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