Submission #564376

#	Time	Username	Problem	Language	Result	Execution time	Memory
564376		Kanon	Fountain Parks (IOI21_parks)	C++17	0 / 100	1 ms	340 KiB

parks

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

using namespace std;

template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}

template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__);

class dsu {
 public:
  vector<int> p;
  int n;

  dsu(){};

  dsu(int _n) : n(_n) {
    p.resize(n);
    iota(p.begin(), p.end(), 0);
  }

  inline int get(int x) {
    return (x == p[x] ? x : (p[x] = get(p[x])));
  }

  inline bool unite(int x, int y) {
    x = get(x);
    y = get(y);
    if (x != y) {
      p[x] = y;
      return true;
    }
    return false;
  }
};

int construct_roads (vector<int> xvec, vector<int> yvec) {
  int N = xvec.size();

  map<pair<int, int>, int> to_v;
  for (int i = 0; i < N; i++) {
    to_v[make_pair(xvec[i], yvec[i])] = i;
  }

  auto get_v = [&](int X, int Y) {
    if (to_v.count(make_pair(X, Y))) {
      return to_v[make_pair(X, Y)];
    }
    return -1;
  };

  int n = 0;
  vector<vector<int>> g;
  map<pair<int, int>, int> to_face;
  vector<pair<int, int>> bench;
  auto get_face = [&](int X, int Y) {
    if (to_face.count(make_pair(X, Y))) {
      return to_face[make_pair(X, Y)];
    }
    bench.push_back({X, Y});
    g.push_back({});
    return to_face[make_pair(X, Y)] = n++;
  };

  int m = 0;
  vector<int> node1, node2, face1, face2;
  dsu fountain(N);
  int is_connected = N;
  auto make_edge = [&] (int x, int y, int X, int Y) {
    int u = get_v(x, y), v = get_v(X, Y);
    if (v == -1) {
      return;
    }
    node1.push_back(u);
    node2.push_back(v);
    is_connected -= fountain.unite(u, v);

    int f1, f2;
    if (x == X) {
      f1 = get_face(x + 1, (y + Y) / 2);
      f2 = get_face(x - 1, (y + Y) / 2);
    } else {
      f1 = get_face((x + X) / 2, y + 1);
      f2 = get_face((x + X) / 2, y - 1);
    }

    g[f1].push_back(m);
    g[f2].push_back(m);
    face1.push_back(f1);
    face2.push_back(f2);
    m++;
  };

  for (int i = 0; i < N; i++) {
    int x = xvec[i], y = yvec[i];
    make_edge(x, y, x + 2, y);
    make_edge(x, y, x, y + 2);
  }

  if (is_connected > 1) {
    return 0;
  }

  vector<int> removal(m);
  vector<int> is_deg4(n);
  for (int i = 0; i < n; i++) {
    is_deg4[i] = g[i].size() == 4;
    assert(g[i].size() <= 4 && g[i].size() != 3 && g[i].size() != 0);
  }

  vector<vector<int>> nodes;
  vector<vector<int>> edges;

  {
    vector<vector<int>> gr(m);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j + 1 < (int) g[i].size(); j += 2) {
        int e1 = g[i][j], e2 = g[i][j + 1];
        gr[e1].push_back(e2);
        gr[e2].push_back(e1);
      }
    }

    vector<int> used(m);
    vector<int> way;
    vector<int> path;
    auto gen = [&] (int v, int e) {
      way = {v};
      path = {e};
      used[e] = 1;
      while (true) {
        int new_v = face1[e] ^ face2[e] ^ v;
        int new_e = -1;
        for (int i : gr[e]) {
          if ((face1[i] == new_v || face2[i] == new_v) && !used[i]) {
            assert(new_e == -1);
            new_e = i;
          }
        }
        swap(v, new_v);
        swap(e, new_e);
        way.push_back(v);
        if (e == -1) {
          break;
        }
        path.push_back(e);
        used[e] = 1;
      }
    };

    vector<int> in_queue(n);
    int iter = 0;
    auto add = [&] () {
      iter++;
      int sz = way.size();
      vector<int> que = {way[0]};
      vector<int> stk;
      in_queue[way[0]] = iter;
      for (int i = 1; i < sz; i++) {
        int v = way[i];
        if (in_queue[v] == iter) {
          nodes.push_back({v});
          edges.push_back({path[i - 1]});
          while (que.back() != v) {
            nodes.back().push_back(que.back());
            edges.back().push_back(stk.back());
            in_queue[que.back()] = 0;
            que.pop_back();
            stk.pop_back();
          }
        } else {
          que.push_back(v);
          stk.push_back(path[i - 1]);
          in_queue[v] = iter;
        }
      }
      if (stk.size()) {
        nodes.push_back(que);
        edges.push_back(stk);
      }

    };

    for (int e = 0; e < m; e++) {
      if (gr[e].size() == 1) {
        int u = face1[e];
        if (g[u].size() % 2 == 0) {
          u = face2[e];
        }
        gen(u, e);
        add();
      }
    }

  }

  int sz = nodes.size();
  vector<int> que;
  vector<vector<int>> relaxed(n);
  vector<int> was(sz);

  for (int i = 0; i < sz; i++) {
    for (int j : nodes[i]) {
      relaxed[j].push_back(i);
    }
    bool ok = false;
    for (int j : nodes[i]) {
      if (!is_deg4[j]) {
        ok = true;
      }
    }
    if (ok) {
      que.push_back(i);
      was[i] = 1;
    }
  }

  for (int b = 0; b < (int) que.size(); b++) {
    int i = que[b];
    for (int j = 0; j < (int) edges[i].size(); j++) {
      int v = nodes[i][j], e = edges[i][j];
      if (is_deg4[v]) {
        removal[e] = 1;
        is_deg4[v] = 0;
        for (int t : relaxed[v]) {
          if (!was[t]) {
            que.push_back(t);
            was[t] = 1;
          }
        }
      }
    }
  }
  /*debug(bench)
  {
    vector<pair<int, int>> bug;
    for (int i = 0; i < m; i++) {
      bug.push_back({face1[i], face2[i]});
    }
    debug(bug);
  }
  debug(removal);
  for (int i = 0; i < m; i++) {
    if (removal[i]) {
      debug(face1[i], face2[i]);
    }
  }*/

  assert((int) que.size() == sz);
  vector<int> visited(n);
  vector<int> parent(n);
  vector<int> paired(m, -1);
  int back_edge = -1;
  int from = -1;

  function<void(int, int)> dfs = [&](int v, int ed) {
    parent[v] = ed;
    visited[v] = 1;
    paired[ed] = v;
    for (int e : g[v]) {
      if (removal[e] || e == ed) {
        continue;
      }
      int u = face1[e] ^ face2[e] ^ v;
      if (visited[u]) {
        assert(back_edge == -1 || back_edge == e);
        if (back_edge == e) {
          continue;
        }
        back_edge = e;
        from = u;
        continue;
      }
      dfs(u, e);
    }
  };

  for (int v = 0; v < n; v++) {
    if (visited[v]) {
      continue;
    }
    dfs(v, -1);
    while(back_edge != -1) {
      paired[back_edge] = from;
      back_edge = parent[from];
      if (back_edge != -1) {
        from = face1[back_edge] ^ face2[back_edge] ^ from;
      } else {
        from = -1;
      }
    }
  }

  dsu d(N);
  int still_connected = N;
  /*auto build = [&] (vector<int> ru, vector<int> rv, vector<int> rx, vector<int> ry) {
    int S = ru.size();
    for (int i = 0; i < S; i++) {
      int x = xvec[ru[i]], y = yvec[ru[i]], X = xvec[rv[i]], Y = yvec[rv[i]];
      cout << "" << x << " " << y << " " << X << " " << Y;
      cout << "\n" << rx[i] << " " << ry[i] << endl;
      //cout << "Segment " << rx[i] << " " << ry[i] << " " << (x + X) / 2 << " " << (y + Y) / 2 << endl;
    }
  };*/

  vector<int> ru, rv, rx, ry;
  for (int e = 0; e < m; e++) {
    if (removal[e]) {
      continue;
    }
    assert(paired[e] != -1);
    ru.push_back(node1[e]);
    rv.push_back(node2[e]);
    still_connected -= d.unite(node1[e], node2[e]);
    int id = paired[e];
    assert(~id);
    rx.push_back(bench[id].first);
    ry.push_back(bench[id].second);
  }
  build(ru, rv, rx, ry);
  assert(still_connected == 1);
  return 1;
}

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