oj.uz

Submission #564798

# Submission time Handle Problem Language Result Execution time Memory
564798 2022-05-19T16:23:15 Z Kanon Fountain Parks (IOI21_parks) C++17
5 / 100
 1615 ms 151316 KB 
#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<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);
     // debug(way)
      //debug(graph)
      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;
        }
      }
     // debug(i, que)
      //assert(que.size() == 1 && que[0] == i);
      que.pop_back();
      in_queue[i] = 0;
    }
  }
  //debug(nodes)
 
  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;
          }
        }
      }
    }
  }
  //assert((int) que.size() == sz);
 
  /*auto build = [&] (vector<int> ru, vector<int> rv, vector<int> rx, vector<int> ry) {
    dsu d(N);
    int still_connected = N;
    set<pair<int, int>> checker;
    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]];
      assert(checker.find({rx[i], ry[i]}) == checker.end());
      checker.insert({rx[i], ry[i]});
      if (x == X) {
        assert(abs(rx[i] - X) == 1 && ry[i] == (Y + y) / 2);
      } else {
        assert(abs(ry[i] - Y) == 1 && rx[i] == (X + x) / 2);
      }
      still_connected -= d.unite(ru[i], rv[i]);
      //cout << "" << x << " " << y << " " << X << " " << Y;
 
      //cout << "\n" << rx[i] << " " << ry[i] << "\n";
    }
    assert(still_connected == 1);
  };*/
 
  vector<int> ru, rv, rx, ry;
  for (int e = 0; e < m; e++) {
    //assert(paired[e] != -1);
    ru.push_back(node1[e]);
    rv.push_back(node2[e]);
    int x = xvec[node1[e]], y = yvec[node1[e]], X = xvec[node2[e]], Y = yvec[node2[e]];
    rx.push_back(x + 1);
    ry.push_back((y + Y) / 2) ;
  }
  build(ru, rv, rx, ry);
  return 1;
}

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:341:49: warning: unused variable 'X' [-Wunused-variable]
  341 |     int x = xvec[node1[e]], y = yvec[node1[e]], X = xvec[node2[e]], Y = yvec[node2[e]];
      |                                                 ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 623 ms 75664 KB Output is correct
10 Correct 36 ms 7812 KB Output is correct
11 Correct 288 ms 40840 KB Output is correct
12 Correct 63 ms 11468 KB Output is correct
13 Correct 95 ms 16104 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 4 ms 980 KB Output is correct
16 Correct 639 ms 75620 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 623 ms 75664 KB Output is correct
10 Correct 36 ms 7812 KB Output is correct
11 Correct 288 ms 40840 KB Output is correct
12 Correct 63 ms 11468 KB Output is correct
13 Correct 95 ms 16104 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 4 ms 980 KB Output is correct
16 Correct 639 ms 75620 KB Output is correct
17 Incorrect 1 ms 212 KB b[0] = 4 is not an odd integer
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 623 ms 75664 KB Output is correct
10 Correct 36 ms 7812 KB Output is correct
11 Correct 288 ms 40840 KB Output is correct
12 Correct 63 ms 11468 KB Output is correct
13 Correct 95 ms 16104 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 4 ms 980 KB Output is correct
16 Correct 639 ms 75620 KB Output is correct
17 Incorrect 1 ms 212 KB b[0] = 4 is not an odd integer
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 623 ms 75664 KB Output is correct
10 Correct 36 ms 7812 KB Output is correct
11 Correct 288 ms 40840 KB Output is correct
12 Correct 63 ms 11468 KB Output is correct
13 Correct 95 ms 16104 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 4 ms 980 KB Output is correct
16 Correct 639 ms 75620 KB Output is correct
17 Incorrect 1 ms 212 KB b[1] = 2 is not an odd integer
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 623 ms 75664 KB Output is correct
10 Correct 36 ms 7812 KB Output is correct
11 Correct 288 ms 40840 KB Output is correct
12 Correct 63 ms 11468 KB Output is correct
13 Correct 95 ms 16104 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 4 ms 980 KB Output is correct
16 Correct 639 ms 75620 KB Output is correct
17 Incorrect 1615 ms 151316 KB b[0] = 100002 is not an odd integer
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 623 ms 75664 KB Output is correct
10 Correct 36 ms 7812 KB Output is correct
11 Correct 288 ms 40840 KB Output is correct
12 Correct 63 ms 11468 KB Output is correct
13 Correct 95 ms 16104 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 4 ms 980 KB Output is correct
16 Correct 639 ms 75620 KB Output is correct
17 Incorrect 1 ms 212 KB b[0] = 4 is not an odd integer
18 Halted 0 ms 0 KB -