Submission #564910

#	Time	Username	Problem	Language	Result	Execution time	Memory
564910		Kanon	Fountain Parks (IOI21_parks)	C++17	100 / 100	2514 ms	151116 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 matching {
  public:
  vector< vector<int> > g;
  vector<int> pa;
  vector<int> pb;
  vector<int> was;
  int n, m;
  int res;
  int iter;

  matching(int _n, int _m) : n(_n), m(_m) {
    assert(0 <= n && 0 <= m);
    pa = vector<int>(n, -1);
    pb = vector<int>(m, -1);
    was = vector<int>(n, 0);
    g.resize(n);
    res = 0;
    iter = 0;
  }

  void add(int from, int to) {
    assert(0 <= from && from < n && 0 <= to && to < m);
    g[from].push_back(to);
  }

  bool dfs(int v) {
    was[v] = iter;
    for (int u : g[v]) {
      if (pb[u] == -1) {
        pa[v] = u;
        pb[u] = v;
        return true;
      }
    }
    for (int u : g[v]) {
      if (was[pb[u]] != iter && dfs(pb[u])) {
        pa[v] = u;
        pb[u] = v;
        return true;
      }
    }
    return false;
  }

  int solve() {
    while (true) {
      iter++;
      int add = 0;
      for (int i = 0; i < n; i++) {
        if (pa[i] == -1 && dfs(i)) {
          add++;
        }
      }
      if (add == 0) {
        break;
      }
      res += add;
    }
    return res;
  }

  int run_one(int v) {
    if (pa[v] != -1) {
      return 0;
    }
    iter++;
    return (int) dfs(v);
  }
};

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;
  }
  vector<vector<int>> nodes;

  {
    vector<set<int>> graph(n + 1);
    for (int e = 0; e < m; e++) {
      int u = face1[e], v = face2[e];
      graph[u].insert(v);
      graph[v].insert(u);
    }
    for (int i = 0; i < n; i++) {
      if (graph[i].size() & 1) {
        graph[i].insert(n);
        graph[n].insert(i);
      }
    }
    vector<int> way;
    function<void(int)> dfs = [&](int v) {
      vector<int> que = {v};
      while (que.size()) {
        int u = que.back();
        if (graph[u].empty()) {
          way.push_back(u);
          que.pop_back();
        } else {
          int b = *graph[u].begin();
          graph[u].erase(b);
          graph[b].erase(u);
          que.push_back(b);
        }
      }
    };

    vector<int> que;
    vector<int> in_queue(n + 1);
    for (int i = n; i >= 0; i--) {
      if (graph[i].empty()) {
        continue;
      }
      way.clear();
      dfs(i);
      for (int v : way) {
        if (in_queue[v]) {
          nodes.push_back({});
          while (que.back() != v) {
            nodes.back().push_back(que.back());
            in_queue[que.back()] = 0;
            que.pop_back();
          }
          nodes.back().push_back(v);
        } else {
          que.push_back(v);
          in_queue[v] = 1;
        }
      }
      que.pop_back();
      in_queue[i] = 0;
    }
  }

  int sz = nodes.size();
  vector<vector<int>> edges;
  {
    map<pair<int, int>, int> cur;
    for (int e = 0; e < m; e++) {
      int u = face1[e], v = face2[e];
      cur[make_pair(u, v)] = e;
      cur[make_pair(v, u)] = e;
    }
    for (auto &p : nodes) {
      edges.push_back({});
      for (int i = 0; i < (int) p.size(); i++) {
        int u = p[i], v = p[(i + 1) % p.size()];
        if (cur.count(make_pair(u, v))) {
          edges.back().push_back(cur[make_pair(u, v)]);
        }
      }
      if (p.back() == n) {
        p.pop_back();
      }
    }
  }
  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;
          }
        }
      }
    }
  }
  vector<int> paired(m, -1);
  matching mt(m, n);
  int cnt = m;
  for (int e = 0; e < m; e++) {
    if (removal[e]) {
      cnt--;
      continue;
    }
    mt.add(e, face1[e]);
    mt.add(e, face2[e]);
  }
  /*vector<int> visited(n);

  function<void(int, int)> dfs = [&] (int v, int ed) {
    visited[v] = 1;
    if (ed != -1) {
      mt.pa[ed] = v;
    }
    for (int e : g[v]) {
      if (removal[e]) {
        continue;
      }
      int u = face1[e] ^ face2[e] ^ v;
      if (visited[u]) {
        continue;
      }
      dfs(u, e);
    }
  };

  for (int i = 0; i < n; i++) {
    if (visited[i]) {
      continue;
    }
    dfs(i, -1);
  }*/

  mt.solve();

  for (int e = 0; e < m; e++) {
    if (removal[e]) {
      continue;
    }
    paired[e] = mt.pa[e];
  }

  vector<int> ru, rv, rx, ry;
  for (int e = 0; e < m; e++) {
    if (removal[e]) {
      continue;
    }
    ru.push_back(node1[e]);
    rv.push_back(node2[e]);
    int id = paired[e];
    rx.push_back(bench[id].first);
    ry.push_back(bench[id].second);
  }
  build(ru, rv, rx, ry);
  return 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