oj.uz

Submission #564910

# Submission time Handle Problem Language Result Execution time Memory
564910 2022-05-20T01:24:04 Z Kanon Fountain Parks (IOI21_parks) C++17
100 / 100
 2514 ms 151116 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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 620 ms 74876 KB Output is correct
10 Correct 38 ms 7848 KB Output is correct
11 Correct 253 ms 40412 KB Output is correct
12 Correct 60 ms 11372 KB Output is correct
13 Correct 95 ms 15716 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 4 ms 980 KB Output is correct
16 Correct 624 ms 74760 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 620 ms 74876 KB Output is correct
10 Correct 38 ms 7848 KB Output is correct
11 Correct 253 ms 40412 KB Output is correct
12 Correct 60 ms 11372 KB Output is correct
13 Correct 95 ms 15716 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 4 ms 980 KB Output is correct
16 Correct 624 ms 74760 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 2165 ms 127528 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 5 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 699 ms 51116 KB Output is correct
29 Correct 1156 ms 77224 KB Output is correct
30 Correct 1590 ms 102112 KB Output is correct
31 Correct 2107 ms 127960 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 0 ms 212 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Correct 0 ms 212 KB Output is correct
39 Correct 0 ms 212 KB Output is correct
40 Correct 1 ms 212 KB Output is correct
41 Correct 0 ms 212 KB Output is correct
42 Correct 1 ms 212 KB Output is correct
43 Correct 4 ms 724 KB Output is correct
44 Correct 6 ms 1184 KB Output is correct
45 Correct 598 ms 53860 KB Output is correct
46 Correct 973 ms 78656 KB Output is correct
47 Correct 1010 ms 78640 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 620 ms 74876 KB Output is correct
10 Correct 38 ms 7848 KB Output is correct
11 Correct 253 ms 40412 KB Output is correct
12 Correct 60 ms 11372 KB Output is correct
13 Correct 95 ms 15716 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 4 ms 980 KB Output is correct
16 Correct 624 ms 74760 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 2165 ms 127528 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 5 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 699 ms 51116 KB Output is correct
29 Correct 1156 ms 77224 KB Output is correct
30 Correct 1590 ms 102112 KB Output is correct
31 Correct 2107 ms 127960 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 0 ms 212 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Correct 0 ms 212 KB Output is correct
39 Correct 0 ms 212 KB Output is correct
40 Correct 1 ms 212 KB Output is correct
41 Correct 0 ms 212 KB Output is correct
42 Correct 1 ms 212 KB Output is correct
43 Correct 4 ms 724 KB Output is correct
44 Correct 6 ms 1184 KB Output is correct
45 Correct 598 ms 53860 KB Output is correct
46 Correct 973 ms 78656 KB Output is correct
47 Correct 1010 ms 78640 KB Output is correct
48 Correct 0 ms 212 KB Output is correct
49 Correct 0 ms 212 KB Output is correct
50 Correct 0 ms 212 KB Output is correct
51 Correct 0 ms 212 KB Output is correct
52 Correct 0 ms 212 KB Output is correct
53 Correct 1 ms 212 KB Output is correct
54 Correct 0 ms 212 KB Output is correct
55 Correct 2356 ms 119584 KB Output is correct
56 Correct 1 ms 212 KB Output is correct
57 Correct 8 ms 1360 KB Output is correct
58 Correct 29 ms 3764 KB Output is correct
59 Correct 24 ms 3316 KB Output is correct
60 Correct 947 ms 60372 KB Output is correct
61 Correct 1429 ms 82140 KB Output is correct
62 Correct 1844 ms 100780 KB Output is correct
63 Correct 2332 ms 121292 KB Output is correct
64 Correct 1 ms 212 KB Output is correct
65 Correct 1 ms 296 KB Output is correct
66 Correct 1 ms 304 KB Output is correct
67 Correct 1372 ms 150968 KB Output is correct
68 Correct 1366 ms 150964 KB Output is correct
69 Correct 1364 ms 150268 KB Output is correct
70 Correct 8 ms 1364 KB Output is correct
71 Correct 16 ms 2448 KB Output is correct
72 Correct 641 ms 54576 KB Output is correct
73 Correct 1040 ms 82660 KB Output is correct
74 Correct 1546 ms 109156 KB Output is correct
75 Correct 1752 ms 122740 KB Output is correct
76 Correct 1395 ms 150964 KB Output is correct
77 Correct 10 ms 1720 KB Output is correct
78 Correct 19 ms 2832 KB Output is correct
79 Correct 696 ms 58096 KB Output is correct
80 Correct 1171 ms 86568 KB Output is correct
81 Correct 1622 ms 116096 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 620 ms 74876 KB Output is correct
10 Correct 38 ms 7848 KB Output is correct
11 Correct 253 ms 40412 KB Output is correct
12 Correct 60 ms 11372 KB Output is correct
13 Correct 95 ms 15716 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 4 ms 980 KB Output is correct
16 Correct 624 ms 74760 KB Output is correct
17 Correct 0 ms 256 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1196 ms 83752 KB Output is correct
21 Correct 1380 ms 84896 KB Output is correct
22 Correct 1231 ms 84656 KB Output is correct
23 Correct 1183 ms 127188 KB Output is correct
24 Correct 419 ms 16736 KB Output is correct
25 Correct 948 ms 70236 KB Output is correct
26 Correct 938 ms 70132 KB Output is correct
27 Correct 1403 ms 149008 KB Output is correct
28 Correct 1426 ms 149096 KB Output is correct
29 Correct 1456 ms 149064 KB Output is correct
30 Correct 1463 ms 149224 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 63 ms 7596 KB Output is correct
33 Correct 163 ms 9676 KB Output is correct
34 Correct 1366 ms 85716 KB Output is correct
35 Correct 24 ms 2916 KB Output is correct
36 Correct 177 ms 13312 KB Output is correct
37 Correct 374 ms 26500 KB Output is correct
38 Correct 486 ms 42236 KB Output is correct
39 Correct 712 ms 56224 KB Output is correct
40 Correct 996 ms 71832 KB Output is correct
41 Correct 1287 ms 88396 KB Output is correct
42 Correct 1574 ms 102192 KB Output is correct
43 Correct 1 ms 212 KB Output is correct
44 Correct 1 ms 212 KB Output is correct
45 Correct 1 ms 212 KB Output is correct
46 Correct 1 ms 256 KB Output is correct
47 Correct 1 ms 300 KB Output is correct
48 Correct 1 ms 296 KB Output is correct
49 Correct 1 ms 212 KB Output is correct
50 Correct 1 ms 212 KB Output is correct
51 Correct 1 ms 296 KB Output is correct
52 Correct 1 ms 212 KB Output is correct
53 Correct 0 ms 212 KB Output is correct
54 Correct 4 ms 852 KB Output is correct
55 Correct 6 ms 1236 KB Output is correct
56 Correct 637 ms 54800 KB Output is correct
57 Correct 991 ms 79936 KB Output is correct
58 Correct 1035 ms 79780 KB Output is correct
59 Correct 1 ms 212 KB Output is correct
60 Correct 1 ms 300 KB Output is correct
61 Correct 1 ms 212 KB Output is correct
62 Correct 1401 ms 151028 KB Output is correct
63 Correct 1383 ms 151116 KB Output is correct
64 Correct 1399 ms 150288 KB Output is correct
65 Correct 8 ms 1364 KB Output is correct
66 Correct 19 ms 2416 KB Output is correct
67 Correct 608 ms 54540 KB Output is correct
68 Correct 1083 ms 82648 KB Output is correct
69 Correct 1502 ms 109084 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 620 ms 74876 KB Output is correct
10 Correct 38 ms 7848 KB Output is correct
11 Correct 253 ms 40412 KB Output is correct
12 Correct 60 ms 11372 KB Output is correct
13 Correct 95 ms 15716 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 4 ms 980 KB Output is correct
16 Correct 624 ms 74760 KB Output is correct
17 Correct 1462 ms 149316 KB Output is correct
18 Correct 1368 ms 149392 KB Output is correct
19 Correct 1321 ms 90088 KB Output is correct
20 Correct 1837 ms 117172 KB Output is correct
21 Correct 1410 ms 121244 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 167 ms 17652 KB Output is correct
24 Correct 50 ms 5824 KB Output is correct
25 Correct 256 ms 19820 KB Output is correct
26 Correct 533 ms 34396 KB Output is correct
27 Correct 709 ms 57100 KB Output is correct
28 Correct 954 ms 71532 KB Output is correct
29 Correct 1191 ms 85732 KB Output is correct
30 Correct 1447 ms 99328 KB Output is correct
31 Correct 1703 ms 113428 KB Output is correct
32 Correct 1650 ms 122852 KB Output is correct
33 Correct 1353 ms 151040 KB Output is correct
34 Correct 10 ms 1748 KB Output is correct
35 Correct 21 ms 2904 KB Output is correct
36 Correct 651 ms 58084 KB Output is correct
37 Correct 1143 ms 86656 KB Output is correct
38 Correct 1627 ms 116024 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 620 ms 74876 KB Output is correct
10 Correct 38 ms 7848 KB Output is correct
11 Correct 253 ms 40412 KB Output is correct
12 Correct 60 ms 11372 KB Output is correct
13 Correct 95 ms 15716 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 4 ms 980 KB Output is correct
16 Correct 624 ms 74760 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 2165 ms 127528 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 5 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 699 ms 51116 KB Output is correct
29 Correct 1156 ms 77224 KB Output is correct
30 Correct 1590 ms 102112 KB Output is correct
31 Correct 2107 ms 127960 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 0 ms 212 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Correct 0 ms 212 KB Output is correct
39 Correct 0 ms 212 KB Output is correct
40 Correct 1 ms 212 KB Output is correct
41 Correct 0 ms 212 KB Output is correct
42 Correct 1 ms 212 KB Output is correct
43 Correct 4 ms 724 KB Output is correct
44 Correct 6 ms 1184 KB Output is correct
45 Correct 598 ms 53860 KB Output is correct
46 Correct 973 ms 78656 KB Output is correct
47 Correct 1010 ms 78640 KB Output is correct
48 Correct 0 ms 212 KB Output is correct
49 Correct 0 ms 212 KB Output is correct
50 Correct 0 ms 212 KB Output is correct
51 Correct 0 ms 212 KB Output is correct
52 Correct 0 ms 212 KB Output is correct
53 Correct 1 ms 212 KB Output is correct
54 Correct 0 ms 212 KB Output is correct
55 Correct 2356 ms 119584 KB Output is correct
56 Correct 1 ms 212 KB Output is correct
57 Correct 8 ms 1360 KB Output is correct
58 Correct 29 ms 3764 KB Output is correct
59 Correct 24 ms 3316 KB Output is correct
60 Correct 947 ms 60372 KB Output is correct
61 Correct 1429 ms 82140 KB Output is correct
62 Correct 1844 ms 100780 KB Output is correct
63 Correct 2332 ms 121292 KB Output is correct
64 Correct 1 ms 212 KB Output is correct
65 Correct 1 ms 296 KB Output is correct
66 Correct 1 ms 304 KB Output is correct
67 Correct 1372 ms 150968 KB Output is correct
68 Correct 1366 ms 150964 KB Output is correct
69 Correct 1364 ms 150268 KB Output is correct
70 Correct 8 ms 1364 KB Output is correct
71 Correct 16 ms 2448 KB Output is correct
72 Correct 641 ms 54576 KB Output is correct
73 Correct 1040 ms 82660 KB Output is correct
74 Correct 1546 ms 109156 KB Output is correct
75 Correct 1752 ms 122740 KB Output is correct
76 Correct 1395 ms 150964 KB Output is correct
77 Correct 10 ms 1720 KB Output is correct
78 Correct 19 ms 2832 KB Output is correct
79 Correct 696 ms 58096 KB Output is correct
80 Correct 1171 ms 86568 KB Output is correct
81 Correct 1622 ms 116096 KB Output is correct
82 Correct 0 ms 256 KB Output is correct
83 Correct 0 ms 212 KB Output is correct
84 Correct 0 ms 212 KB Output is correct
85 Correct 1196 ms 83752 KB Output is correct
86 Correct 1380 ms 84896 KB Output is correct
87 Correct 1231 ms 84656 KB Output is correct
88 Correct 1183 ms 127188 KB Output is correct
89 Correct 419 ms 16736 KB Output is correct
90 Correct 948 ms 70236 KB Output is correct
91 Correct 938 ms 70132 KB Output is correct
92 Correct 1403 ms 149008 KB Output is correct
93 Correct 1426 ms 149096 KB Output is correct
94 Correct 1456 ms 149064 KB Output is correct
95 Correct 1463 ms 149224 KB Output is correct
96 Correct 1 ms 212 KB Output is correct
97 Correct 63 ms 7596 KB Output is correct
98 Correct 163 ms 9676 KB Output is correct
99 Correct 1366 ms 85716 KB Output is correct
100 Correct 24 ms 2916 KB Output is correct
101 Correct 177 ms 13312 KB Output is correct
102 Correct 374 ms 26500 KB Output is correct
103 Correct 486 ms 42236 KB Output is correct
104 Correct 712 ms 56224 KB Output is correct
105 Correct 996 ms 71832 KB Output is correct
106 Correct 1287 ms 88396 KB Output is correct
107 Correct 1574 ms 102192 KB Output is correct
108 Correct 1 ms 212 KB Output is correct
109 Correct 1 ms 212 KB Output is correct
110 Correct 1 ms 212 KB Output is correct
111 Correct 1 ms 256 KB Output is correct
112 Correct 1 ms 300 KB Output is correct
113 Correct 1 ms 296 KB Output is correct
114 Correct 1 ms 212 KB Output is correct
115 Correct 1 ms 212 KB Output is correct
116 Correct 1 ms 296 KB Output is correct
117 Correct 1 ms 212 KB Output is correct
118 Correct 0 ms 212 KB Output is correct
119 Correct 4 ms 852 KB Output is correct
120 Correct 6 ms 1236 KB Output is correct
121 Correct 637 ms 54800 KB Output is correct
122 Correct 991 ms 79936 KB Output is correct
123 Correct 1035 ms 79780 KB Output is correct
124 Correct 1 ms 212 KB Output is correct
125 Correct 1 ms 300 KB Output is correct
126 Correct 1 ms 212 KB Output is correct
127 Correct 1401 ms 151028 KB Output is correct
128 Correct 1383 ms 151116 KB Output is correct
129 Correct 1399 ms 150288 KB Output is correct
130 Correct 8 ms 1364 KB Output is correct
131 Correct 19 ms 2416 KB Output is correct
132 Correct 608 ms 54540 KB Output is correct
133 Correct 1083 ms 82648 KB Output is correct
134 Correct 1502 ms 109084 KB Output is correct
135 Correct 1462 ms 149316 KB Output is correct
136 Correct 1368 ms 149392 KB Output is correct
137 Correct 1321 ms 90088 KB Output is correct
138 Correct 1837 ms 117172 KB Output is correct
139 Correct 1410 ms 121244 KB Output is correct
140 Correct 1 ms 212 KB Output is correct
141 Correct 167 ms 17652 KB Output is correct
142 Correct 50 ms 5824 KB Output is correct
143 Correct 256 ms 19820 KB Output is correct
144 Correct 533 ms 34396 KB Output is correct
145 Correct 709 ms 57100 KB Output is correct
146 Correct 954 ms 71532 KB Output is correct
147 Correct 1191 ms 85732 KB Output is correct
148 Correct 1447 ms 99328 KB Output is correct
149 Correct 1703 ms 113428 KB Output is correct
150 Correct 1650 ms 122852 KB Output is correct
151 Correct 1353 ms 151040 KB Output is correct
152 Correct 10 ms 1748 KB Output is correct
153 Correct 21 ms 2904 KB Output is correct
154 Correct 651 ms 58084 KB Output is correct
155 Correct 1143 ms 86656 KB Output is correct
156 Correct 1627 ms 116024 KB Output is correct
157 Correct 1 ms 212 KB Output is correct
158 Correct 0 ms 296 KB Output is correct
159 Correct 1 ms 212 KB Output is correct
160 Correct 1 ms 212 KB Output is correct
161 Correct 2514 ms 110844 KB Output is correct
162 Correct 1368 ms 85504 KB Output is correct
163 Correct 1631 ms 98988 KB Output is correct
164 Correct 1646 ms 99204 KB Output is correct
165 Correct 2120 ms 104160 KB Output is correct
166 Correct 2363 ms 109268 KB Output is correct
167 Correct 338 ms 25092 KB Output is correct
168 Correct 98 ms 7900 KB Output is correct
169 Correct 364 ms 22000 KB Output is correct
170 Correct 844 ms 41144 KB Output is correct
171 Correct 1255 ms 52716 KB Output is correct
172 Correct 1044 ms 55688 KB Output is correct
173 Correct 1279 ms 66368 KB Output is correct
174 Correct 1590 ms 79924 KB Output is correct
175 Correct 1875 ms 90080 KB Output is correct
176 Correct 2219 ms 100324 KB Output is correct
177 Correct 2484 ms 110620 KB Output is correct