oj.uz

답안 #564909

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
564909 2022-05-20T01:21:15 Z Kanon 분수 공원 (IOI21_parks) C++17
15 / 100
 2356 ms 151104 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 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.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 667 ms 75720 KB Output is correct
10 Correct 38 ms 7952 KB Output is correct
11 Correct 271 ms 40968 KB Output is correct
12 Correct 61 ms 11548 KB Output is correct
13 Correct 97 ms 16112 KB Output is correct
14 Correct 2 ms 560 KB Output is correct
15 Correct 4 ms 980 KB Output is correct
16 Correct 686 ms 75584 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 667 ms 75720 KB Output is correct
10 Correct 38 ms 7952 KB Output is correct
11 Correct 271 ms 40968 KB Output is correct
12 Correct 61 ms 11548 KB Output is correct
13 Correct 97 ms 16112 KB Output is correct
14 Correct 2 ms 560 KB Output is correct
15 Correct 4 ms 980 KB Output is correct
16 Correct 686 ms 75584 KB Output is correct
17 Correct 1 ms 292 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 2223 ms 129216 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 6 ms 980 KB Output is correct
26 Correct 6 ms 1236 KB Output is correct
27 Correct 9 ms 1492 KB Output is correct
28 Correct 710 ms 51528 KB Output is correct
29 Correct 1148 ms 78524 KB Output is correct
30 Correct 1639 ms 103424 KB Output is correct
31 Correct 2193 ms 129672 KB Output is correct
32 Correct 1 ms 212 KB Output is correct
33 Correct 1 ms 300 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 1 ms 300 KB Output is correct
37 Correct 1 ms 212 KB Output is correct
38 Correct 1 ms 212 KB Output is correct
39 Correct 1 ms 212 KB Output is correct
40 Correct 1 ms 212 KB Output is correct
41 Correct 1 ms 212 KB Output is correct
42 Correct 0 ms 212 KB Output is correct
43 Correct 4 ms 852 KB Output is correct
44 Correct 7 ms 1204 KB Output is correct
45 Correct 622 ms 55340 KB Output is correct
46 Correct 1000 ms 80636 KB Output is correct
47 Correct 1064 ms 80564 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 667 ms 75720 KB Output is correct
10 Correct 38 ms 7952 KB Output is correct
11 Correct 271 ms 40968 KB Output is correct
12 Correct 61 ms 11548 KB Output is correct
13 Correct 97 ms 16112 KB Output is correct
14 Correct 2 ms 560 KB Output is correct
15 Correct 4 ms 980 KB Output is correct
16 Correct 686 ms 75584 KB Output is correct
17 Correct 1 ms 292 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 2223 ms 129216 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 6 ms 980 KB Output is correct
26 Correct 6 ms 1236 KB Output is correct
27 Correct 9 ms 1492 KB Output is correct
28 Correct 710 ms 51528 KB Output is correct
29 Correct 1148 ms 78524 KB Output is correct
30 Correct 1639 ms 103424 KB Output is correct
31 Correct 2193 ms 129672 KB Output is correct
32 Correct 1 ms 212 KB Output is correct
33 Correct 1 ms 300 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 1 ms 300 KB Output is correct
37 Correct 1 ms 212 KB Output is correct
38 Correct 1 ms 212 KB Output is correct
39 Correct 1 ms 212 KB Output is correct
40 Correct 1 ms 212 KB Output is correct
41 Correct 1 ms 212 KB Output is correct
42 Correct 0 ms 212 KB Output is correct
43 Correct 4 ms 852 KB Output is correct
44 Correct 7 ms 1204 KB Output is correct
45 Correct 622 ms 55340 KB Output is correct
46 Correct 1000 ms 80636 KB Output is correct
47 Correct 1064 ms 80564 KB Output is correct
48 Correct 0 ms 212 KB Output is correct
49 Correct 1 ms 212 KB Output is correct
50 Correct 1 ms 300 KB Output is correct
51 Correct 1 ms 212 KB Output is correct
52 Correct 1 ms 212 KB Output is correct
53 Correct 1 ms 212 KB Output is correct
54 Correct 1 ms 212 KB Output is correct
55 Incorrect 2356 ms 121096 KB Tree @(5, 82687) appears more than once: for edges on positions 1147 and 1148
56 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 667 ms 75720 KB Output is correct
10 Correct 38 ms 7952 KB Output is correct
11 Correct 271 ms 40968 KB Output is correct
12 Correct 61 ms 11548 KB Output is correct
13 Correct 97 ms 16112 KB Output is correct
14 Correct 2 ms 560 KB Output is correct
15 Correct 4 ms 980 KB Output is correct
16 Correct 686 ms 75584 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1263 ms 98276 KB Output is correct
21 Correct 1460 ms 91032 KB Output is correct
22 Correct 1242 ms 91176 KB Output is correct
23 Correct 1176 ms 129976 KB Output is correct
24 Correct 417 ms 18328 KB Output is correct
25 Correct 1006 ms 71800 KB Output is correct
26 Correct 942 ms 71664 KB Output is correct
27 Correct 1416 ms 150668 KB Output is correct
28 Correct 1418 ms 150520 KB Output is correct
29 Correct 1461 ms 150600 KB Output is correct
30 Correct 1449 ms 150708 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Incorrect 59 ms 7824 KB Tree @(185881, 20285) appears more than once: for edges on positions 296 and 297
33 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 667 ms 75720 KB Output is correct
10 Correct 38 ms 7952 KB Output is correct
11 Correct 271 ms 40968 KB Output is correct
12 Correct 61 ms 11548 KB Output is correct
13 Correct 97 ms 16112 KB Output is correct
14 Correct 2 ms 560 KB Output is correct
15 Correct 4 ms 980 KB Output is correct
16 Correct 686 ms 75584 KB Output is correct
17 Correct 1405 ms 150864 KB Output is correct
18 Incorrect 1411 ms 151104 KB Tree @(50003, 50003) appears more than once: for edges on positions 183490 and 183491
19 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 667 ms 75720 KB Output is correct
10 Correct 38 ms 7952 KB Output is correct
11 Correct 271 ms 40968 KB Output is correct
12 Correct 61 ms 11548 KB Output is correct
13 Correct 97 ms 16112 KB Output is correct
14 Correct 2 ms 560 KB Output is correct
15 Correct 4 ms 980 KB Output is correct
16 Correct 686 ms 75584 KB Output is correct
17 Correct 1 ms 292 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 2223 ms 129216 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 6 ms 980 KB Output is correct
26 Correct 6 ms 1236 KB Output is correct
27 Correct 9 ms 1492 KB Output is correct
28 Correct 710 ms 51528 KB Output is correct
29 Correct 1148 ms 78524 KB Output is correct
30 Correct 1639 ms 103424 KB Output is correct
31 Correct 2193 ms 129672 KB Output is correct
32 Correct 1 ms 212 KB Output is correct
33 Correct 1 ms 300 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 1 ms 300 KB Output is correct
37 Correct 1 ms 212 KB Output is correct
38 Correct 1 ms 212 KB Output is correct
39 Correct 1 ms 212 KB Output is correct
40 Correct 1 ms 212 KB Output is correct
41 Correct 1 ms 212 KB Output is correct
42 Correct 0 ms 212 KB Output is correct
43 Correct 4 ms 852 KB Output is correct
44 Correct 7 ms 1204 KB Output is correct
45 Correct 622 ms 55340 KB Output is correct
46 Correct 1000 ms 80636 KB Output is correct
47 Correct 1064 ms 80564 KB Output is correct
48 Correct 0 ms 212 KB Output is correct
49 Correct 1 ms 212 KB Output is correct
50 Correct 1 ms 300 KB Output is correct
51 Correct 1 ms 212 KB Output is correct
52 Correct 1 ms 212 KB Output is correct
53 Correct 1 ms 212 KB Output is correct
54 Correct 1 ms 212 KB Output is correct
55 Incorrect 2356 ms 121096 KB Tree @(5, 82687) appears more than once: for edges on positions 1147 and 1148
56 Halted 0 ms 0 KB -