oj.uz

답안 #526633

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
526633 2022-02-15T19:19:42 Z xiaowuc1 From Hacks to Snitches (BOI21_watchmen) C++17
100 / 100
 2113 ms 176604 KB 
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>

using namespace std;

// BEGIN NO SAD
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
typedef vector<int> vi;
#define f first
#define s second
#define derr if(1) cerr
// END NO SAD

template<class Fun>
class y_combinator_result {
  Fun fun_;
public:
  template<class T>
  explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

  template<class ...Args>
  decltype(auto) operator()(Args &&...args) {
    return fun_(std::ref(*this), std::forward<Args>(args)...);
  }
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
  return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

template<class T>
bool updmin(T& a, T b) {
  if(b < a) {
    a = b;
    return true;
  }
  return false;
}
template<class T>
bool updmax(T& a, T b) {
  if(b > a) {
    a = b;
    return true;
  }
  return false;
}
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<vector<ll>> matrix;

void win(int x) {
  cout << x << "\n";
  exit(0);
}

void solve() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> g(n);
  vector<int> cycleidx(n, -1), cyclepos(n, -1);
  for(int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    g[a].pb(b);
    g[b].pb(a);
  }
  int k;
  cin >> k;
  vector<vector<int>> cycles(k);
  for(int i = 0; i < k; i++) {
    int x;
    cin >> x;
    cycles[i].resize(x);
    for(int j = 0; j < x; j++) {
      cin >> cycles[i][j];
      cycleidx[--cycles[i][j]] = i;
      cyclepos[cycles[i][j]] = j;
    }
  }
  vector<vector<int>> dp(n);
  for(int i = 0; i < n; i++) {
    if(cycleidx[i] < 0) dp[i].resize(1);
    else dp[i].resize(sz(cycles[cycleidx[i]]));
    fill(all(dp[i]), 2e9);
  }
  const int THRESH = n + 1000000;
  vector<vector<int>> can(THRESH);
  auto upd = [&](int v, int w) {
    int idx = w % sz(dp[v]);
    if(cyclepos[v] == idx) return;
    if(updmin(dp[v][idx], w)) can[w].pb(v);
  };
  can[0].pb(0); dp[0][0] = 0;
  for(int ret = 0; ret < THRESH; ret++) {
    for(int currv: can[ret]) {
      int idx = ret % sz(dp[currv]);
      if(dp[currv][idx] != ret) continue;
      if(currv == n-1) win(ret);
      for(int eidx = 0; eidx < sz(g[currv]); eidx++) {
        int cand = g[currv][eidx];
        if(cycleidx[currv] < 0 || cycleidx[currv] != cycleidx[cand] || (cyclepos[cand]+1)%sz(dp[currv]) != cyclepos[currv] || cyclepos[cand] != idx) upd(cand, ret+1);
        if(cycleidx[currv] < 0 && cycleidx[cand] >= 0) upd(cand, ret + 1 + (cyclepos[cand] + sz(dp[cand]) - ret % sz(dp[cand])) % sz(dp[cand]));
        bool dead = false;
        if(cycleidx[currv] >= 0 && cycleidx[cand] >= 0 && (cycleidx[currv] != cycleidx[cand] || ((cyclepos[cand]+1) % sz(dp[currv]) != cyclepos[currv] && (cyclepos[currv]+1) % sz(dp[currv]) != cyclepos[cand]))) {
          int fdist = ret + (cyclepos[cand] + sz(dp[cand]) - ret % sz(dp[cand])) % sz(dp[cand]);
          int gdist = fdist + (cyclepos[currv] + sz(dp[currv]) - fdist % sz(dp[currv])) % sz(dp[currv]);
          if(fdist != gdist) {
            upd(cand, fdist+1);
            dead = true;
          }
          else {
            int dist = fdist + (idx + sz(dp[currv]) - cyclepos[currv]) % sz(dp[currv]);
            upd(cand, dist+1);
            if(sz(dp[cand]) % sz(dp[currv]) && (sz(dp[currv]) % sz(dp[cand]) || (cyclepos[currv] + sz(dp[currv]) - idx) % sz(dp[currv]) >= sz(dp[cand]))) {
              upd(cand, dist+1 + (cyclepos[cand] + sz(dp[cand]) - dist % sz(dp[cand])) % sz(dp[cand]));
            }
          }
        }
        if(cycleidx[currv] < 0 || cycleidx[cand] < 0 || dead) {
          if(eidx+1 < sz(g[currv])) swap(g[currv][eidx], g[currv].back());
          g[currv].pop_back();
          eidx--;
        }
      }
      upd(currv, ret+1);
    }
  }
  cout << "impossible\n";
}

// what would chika do
// are there edge cases (N=1?)
// are array sizes proper (scaled by proper constant, for example 2* for koosaga tree)
// integer overflow?
// DS reset properly between test cases
// are you doing geometry in floating points
// are you not using modint when you should

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  solve();
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 25220 KB Output is correct
2 Correct 81 ms 42288 KB Output is correct
3 Correct 76 ms 39972 KB Output is correct
4 Correct 95 ms 39612 KB Output is correct
5 Correct 11 ms 23844 KB Output is correct
6 Correct 69 ms 39776 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 25412 KB Output is correct
2 Correct 77 ms 42296 KB Output is correct
3 Correct 86 ms 39924 KB Output is correct
4 Correct 70 ms 39532 KB Output is correct
5 Correct 10 ms 23888 KB Output is correct
6 Correct 67 ms 39740 KB Output is correct
7 Correct 68 ms 40108 KB Output is correct
8 Correct 76 ms 40132 KB Output is correct
9 Correct 84 ms 40332 KB Output is correct
10 Correct 75 ms 38804 KB Output is correct
11 Correct 63 ms 38216 KB Output is correct
12 Correct 70 ms 39624 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 25412 KB Output is correct
2 Correct 77 ms 42296 KB Output is correct
3 Correct 86 ms 39924 KB Output is correct
4 Correct 70 ms 39532 KB Output is correct
5 Correct 10 ms 23888 KB Output is correct
6 Correct 67 ms 39740 KB Output is correct
7 Correct 68 ms 40108 KB Output is correct
8 Correct 76 ms 40132 KB Output is correct
9 Correct 84 ms 40332 KB Output is correct
10 Correct 75 ms 38804 KB Output is correct
11 Correct 63 ms 38216 KB Output is correct
12 Correct 70 ms 39624 KB Output is correct
13 Correct 21 ms 25220 KB Output is correct
14 Correct 107 ms 42312 KB Output is correct
15 Correct 85 ms 39920 KB Output is correct
16 Correct 67 ms 39484 KB Output is correct
17 Correct 9 ms 23888 KB Output is correct
18 Correct 70 ms 39700 KB Output is correct
19 Correct 70 ms 40056 KB Output is correct
20 Correct 99 ms 40188 KB Output is correct
21 Correct 87 ms 40292 KB Output is correct
22 Correct 68 ms 38856 KB Output is correct
23 Correct 67 ms 38216 KB Output is correct
24 Correct 74 ms 39624 KB Output is correct
25 Correct 1627 ms 135260 KB Output is correct
26 Correct 1655 ms 140100 KB Output is correct
27 Correct 1520 ms 136312 KB Output is correct
28 Correct 1130 ms 141120 KB Output is correct
29 Correct 1544 ms 128608 KB Output is correct
30 Correct 1474 ms 129204 KB Output is correct
31 Correct 1734 ms 137852 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 25412 KB Output is correct
2 Correct 77 ms 42296 KB Output is correct
3 Correct 86 ms 39924 KB Output is correct
4 Correct 70 ms 39532 KB Output is correct
5 Correct 10 ms 23888 KB Output is correct
6 Correct 67 ms 39740 KB Output is correct
7 Correct 68 ms 40108 KB Output is correct
8 Correct 76 ms 40132 KB Output is correct
9 Correct 84 ms 40332 KB Output is correct
10 Correct 75 ms 38804 KB Output is correct
11 Correct 63 ms 38216 KB Output is correct
12 Correct 70 ms 39624 KB Output is correct
13 Correct 21 ms 25220 KB Output is correct
14 Correct 107 ms 42312 KB Output is correct
15 Correct 85 ms 39920 KB Output is correct
16 Correct 67 ms 39484 KB Output is correct
17 Correct 9 ms 23888 KB Output is correct
18 Correct 70 ms 39700 KB Output is correct
19 Correct 70 ms 40056 KB Output is correct
20 Correct 99 ms 40188 KB Output is correct
21 Correct 87 ms 40292 KB Output is correct
22 Correct 68 ms 38856 KB Output is correct
23 Correct 67 ms 38216 KB Output is correct
24 Correct 74 ms 39624 KB Output is correct
25 Correct 1627 ms 135260 KB Output is correct
26 Correct 1655 ms 140100 KB Output is correct
27 Correct 1520 ms 136312 KB Output is correct
28 Correct 1130 ms 141120 KB Output is correct
29 Correct 1544 ms 128608 KB Output is correct
30 Correct 1474 ms 129204 KB Output is correct
31 Correct 1734 ms 137852 KB Output is correct
32 Correct 25 ms 25216 KB Output is correct
33 Correct 88 ms 42232 KB Output is correct
34 Correct 95 ms 39960 KB Output is correct
35 Correct 72 ms 39496 KB Output is correct
36 Correct 11 ms 23888 KB Output is correct
37 Correct 75 ms 39752 KB Output is correct
38 Correct 98 ms 40088 KB Output is correct
39 Correct 72 ms 40144 KB Output is correct
40 Correct 82 ms 40388 KB Output is correct
41 Correct 75 ms 38844 KB Output is correct
42 Correct 82 ms 38320 KB Output is correct
43 Correct 80 ms 39616 KB Output is correct
44 Correct 1685 ms 135164 KB Output is correct
45 Correct 1551 ms 140096 KB Output is correct
46 Correct 1542 ms 136328 KB Output is correct
47 Correct 1226 ms 141132 KB Output is correct
48 Correct 1472 ms 128704 KB Output is correct
49 Correct 1460 ms 129176 KB Output is correct
50 Correct 1705 ms 137880 KB Output is correct
51 Correct 1983 ms 155988 KB Output is correct
52 Correct 2085 ms 176604 KB Output is correct
53 Correct 1879 ms 157392 KB Output is correct
54 Correct 1116 ms 133888 KB Output is correct
55 Correct 1814 ms 153788 KB Output is correct
56 Correct 1715 ms 140260 KB Output is correct

Subtask #5
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 25220 KB Output is correct
2 Correct 81 ms 42288 KB Output is correct
3 Correct 76 ms 39972 KB Output is correct
4 Correct 95 ms 39612 KB Output is correct
5 Correct 11 ms 23844 KB Output is correct
6 Correct 69 ms 39776 KB Output is correct
7 Correct 21 ms 25412 KB Output is correct
8 Correct 77 ms 42296 KB Output is correct
9 Correct 86 ms 39924 KB Output is correct
10 Correct 70 ms 39532 KB Output is correct
11 Correct 10 ms 23888 KB Output is correct
12 Correct 67 ms 39740 KB Output is correct
13 Correct 68 ms 40108 KB Output is correct
14 Correct 76 ms 40132 KB Output is correct
15 Correct 84 ms 40332 KB Output is correct
16 Correct 75 ms 38804 KB Output is correct
17 Correct 63 ms 38216 KB Output is correct
18 Correct 70 ms 39624 KB Output is correct
19 Correct 11 ms 23760 KB Output is correct
20 Correct 10 ms 23760 KB Output is correct
21 Correct 15 ms 23784 KB Output is correct
22 Correct 22 ms 25280 KB Output is correct
23 Correct 91 ms 42308 KB Output is correct
24 Correct 88 ms 40008 KB Output is correct
25 Correct 92 ms 39496 KB Output is correct
26 Correct 11 ms 23872 KB Output is correct
27 Correct 72 ms 39684 KB Output is correct
28 Correct 75 ms 40120 KB Output is correct
29 Correct 72 ms 40136 KB Output is correct
30 Correct 104 ms 40412 KB Output is correct
31 Correct 69 ms 38752 KB Output is correct
32 Correct 67 ms 38332 KB Output is correct
33 Correct 74 ms 39712 KB Output is correct
34 Correct 1773 ms 133052 KB Output is correct
35 Correct 1844 ms 127888 KB Output is correct
36 Correct 1839 ms 130240 KB Output is correct
37 Correct 1630 ms 135944 KB Output is correct
38 Correct 1726 ms 134848 KB Output is correct
39 Correct 1555 ms 128664 KB Output is correct
40 Correct 1514 ms 128652 KB Output is correct
41 Correct 1526 ms 128572 KB Output is correct
42 Correct 1719 ms 134596 KB Output is correct
43 Correct 1758 ms 134688 KB Output is correct
44 Correct 1809 ms 137308 KB Output is correct
45 Correct 1797 ms 132000 KB Output is correct
46 Correct 1752 ms 134644 KB Output is correct

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 25220 KB Output is correct
2 Correct 81 ms 42288 KB Output is correct
3 Correct 76 ms 39972 KB Output is correct
4 Correct 95 ms 39612 KB Output is correct
5 Correct 11 ms 23844 KB Output is correct
6 Correct 69 ms 39776 KB Output is correct
7 Correct 21 ms 25412 KB Output is correct
8 Correct 77 ms 42296 KB Output is correct
9 Correct 86 ms 39924 KB Output is correct
10 Correct 70 ms 39532 KB Output is correct
11 Correct 10 ms 23888 KB Output is correct
12 Correct 67 ms 39740 KB Output is correct
13 Correct 68 ms 40108 KB Output is correct
14 Correct 76 ms 40132 KB Output is correct
15 Correct 84 ms 40332 KB Output is correct
16 Correct 75 ms 38804 KB Output is correct
17 Correct 63 ms 38216 KB Output is correct
18 Correct 70 ms 39624 KB Output is correct
19 Correct 21 ms 25220 KB Output is correct
20 Correct 107 ms 42312 KB Output is correct
21 Correct 85 ms 39920 KB Output is correct
22 Correct 67 ms 39484 KB Output is correct
23 Correct 9 ms 23888 KB Output is correct
24 Correct 70 ms 39700 KB Output is correct
25 Correct 70 ms 40056 KB Output is correct
26 Correct 99 ms 40188 KB Output is correct
27 Correct 87 ms 40292 KB Output is correct
28 Correct 68 ms 38856 KB Output is correct
29 Correct 67 ms 38216 KB Output is correct
30 Correct 74 ms 39624 KB Output is correct
31 Correct 1627 ms 135260 KB Output is correct
32 Correct 1655 ms 140100 KB Output is correct
33 Correct 1520 ms 136312 KB Output is correct
34 Correct 1130 ms 141120 KB Output is correct
35 Correct 1544 ms 128608 KB Output is correct
36 Correct 1474 ms 129204 KB Output is correct
37 Correct 1734 ms 137852 KB Output is correct
38 Correct 11 ms 23760 KB Output is correct
39 Correct 10 ms 23760 KB Output is correct
40 Correct 15 ms 23784 KB Output is correct
41 Correct 22 ms 25280 KB Output is correct
42 Correct 91 ms 42308 KB Output is correct
43 Correct 88 ms 40008 KB Output is correct
44 Correct 92 ms 39496 KB Output is correct
45 Correct 11 ms 23872 KB Output is correct
46 Correct 72 ms 39684 KB Output is correct
47 Correct 75 ms 40120 KB Output is correct
48 Correct 72 ms 40136 KB Output is correct
49 Correct 104 ms 40412 KB Output is correct
50 Correct 69 ms 38752 KB Output is correct
51 Correct 67 ms 38332 KB Output is correct
52 Correct 74 ms 39712 KB Output is correct
53 Correct 1773 ms 133052 KB Output is correct
54 Correct 1844 ms 127888 KB Output is correct
55 Correct 1839 ms 130240 KB Output is correct
56 Correct 1630 ms 135944 KB Output is correct
57 Correct 1726 ms 134848 KB Output is correct
58 Correct 1555 ms 128664 KB Output is correct
59 Correct 1514 ms 128652 KB Output is correct
60 Correct 1526 ms 128572 KB Output is correct
61 Correct 1719 ms 134596 KB Output is correct
62 Correct 1758 ms 134688 KB Output is correct
63 Correct 1809 ms 137308 KB Output is correct
64 Correct 1797 ms 132000 KB Output is correct
65 Correct 1752 ms 134644 KB Output is correct
66 Correct 10 ms 23760 KB Output is correct
67 Correct 11 ms 23760 KB Output is correct
68 Correct 14 ms 23760 KB Output is correct
69 Correct 21 ms 25232 KB Output is correct
70 Correct 83 ms 42268 KB Output is correct
71 Correct 79 ms 39908 KB Output is correct
72 Correct 82 ms 39512 KB Output is correct
73 Correct 11 ms 23888 KB Output is correct
74 Correct 71 ms 39676 KB Output is correct
75 Correct 91 ms 40120 KB Output is correct
76 Correct 84 ms 40152 KB Output is correct
77 Correct 74 ms 40324 KB Output is correct
78 Correct 74 ms 38836 KB Output is correct
79 Correct 70 ms 38312 KB Output is correct
80 Correct 75 ms 39612 KB Output is correct
81 Correct 1760 ms 135156 KB Output is correct
82 Correct 1606 ms 139876 KB Output is correct
83 Correct 1560 ms 136252 KB Output is correct
84 Correct 1237 ms 140860 KB Output is correct
85 Correct 1481 ms 128608 KB Output is correct
86 Correct 1586 ms 128856 KB Output is correct
87 Correct 1761 ms 137684 KB Output is correct
88 Correct 1658 ms 133252 KB Output is correct
89 Correct 1822 ms 127868 KB Output is correct
90 Correct 1832 ms 130020 KB Output is correct
91 Correct 1535 ms 135776 KB Output is correct
92 Correct 1651 ms 134732 KB Output is correct
93 Correct 1444 ms 128876 KB Output is correct
94 Correct 1456 ms 128824 KB Output is correct
95 Correct 1446 ms 128648 KB Output is correct
96 Correct 1658 ms 134612 KB Output is correct
97 Correct 1651 ms 134760 KB Output is correct
98 Correct 1697 ms 137264 KB Output is correct
99 Correct 1752 ms 132076 KB Output is correct
100 Correct 1636 ms 134688 KB Output is correct
101 Correct 1664 ms 133008 KB Output is correct
102 Correct 1511 ms 135892 KB Output is correct
103 Correct 1627 ms 135068 KB Output is correct
104 Correct 1479 ms 131432 KB Output is correct
105 Correct 1646 ms 135100 KB Output is correct
106 Correct 1750 ms 132056 KB Output is correct
107 Correct 1667 ms 134760 KB Output is correct

Subtask #7
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 25220 KB Output is correct
2 Correct 81 ms 42288 KB Output is correct
3 Correct 76 ms 39972 KB Output is correct
4 Correct 95 ms 39612 KB Output is correct
5 Correct 11 ms 23844 KB Output is correct
6 Correct 69 ms 39776 KB Output is correct
7 Correct 21 ms 25412 KB Output is correct
8 Correct 77 ms 42296 KB Output is correct
9 Correct 86 ms 39924 KB Output is correct
10 Correct 70 ms 39532 KB Output is correct
11 Correct 10 ms 23888 KB Output is correct
12 Correct 67 ms 39740 KB Output is correct
13 Correct 68 ms 40108 KB Output is correct
14 Correct 76 ms 40132 KB Output is correct
15 Correct 84 ms 40332 KB Output is correct
16 Correct 75 ms 38804 KB Output is correct
17 Correct 63 ms 38216 KB Output is correct
18 Correct 70 ms 39624 KB Output is correct
19 Correct 21 ms 25220 KB Output is correct
20 Correct 107 ms 42312 KB Output is correct
21 Correct 85 ms 39920 KB Output is correct
22 Correct 67 ms 39484 KB Output is correct
23 Correct 9 ms 23888 KB Output is correct
24 Correct 70 ms 39700 KB Output is correct
25 Correct 70 ms 40056 KB Output is correct
26 Correct 99 ms 40188 KB Output is correct
27 Correct 87 ms 40292 KB Output is correct
28 Correct 68 ms 38856 KB Output is correct
29 Correct 67 ms 38216 KB Output is correct
30 Correct 74 ms 39624 KB Output is correct
31 Correct 1627 ms 135260 KB Output is correct
32 Correct 1655 ms 140100 KB Output is correct
33 Correct 1520 ms 136312 KB Output is correct
34 Correct 1130 ms 141120 KB Output is correct
35 Correct 1544 ms 128608 KB Output is correct
36 Correct 1474 ms 129204 KB Output is correct
37 Correct 1734 ms 137852 KB Output is correct
38 Correct 25 ms 25216 KB Output is correct
39 Correct 88 ms 42232 KB Output is correct
40 Correct 95 ms 39960 KB Output is correct
41 Correct 72 ms 39496 KB Output is correct
42 Correct 11 ms 23888 KB Output is correct
43 Correct 75 ms 39752 KB Output is correct
44 Correct 98 ms 40088 KB Output is correct
45 Correct 72 ms 40144 KB Output is correct
46 Correct 82 ms 40388 KB Output is correct
47 Correct 75 ms 38844 KB Output is correct
48 Correct 82 ms 38320 KB Output is correct
49 Correct 80 ms 39616 KB Output is correct
50 Correct 1685 ms 135164 KB Output is correct
51 Correct 1551 ms 140096 KB Output is correct
52 Correct 1542 ms 136328 KB Output is correct
53 Correct 1226 ms 141132 KB Output is correct
54 Correct 1472 ms 128704 KB Output is correct
55 Correct 1460 ms 129176 KB Output is correct
56 Correct 1705 ms 137880 KB Output is correct
57 Correct 1983 ms 155988 KB Output is correct
58 Correct 2085 ms 176604 KB Output is correct
59 Correct 1879 ms 157392 KB Output is correct
60 Correct 1116 ms 133888 KB Output is correct
61 Correct 1814 ms 153788 KB Output is correct
62 Correct 1715 ms 140260 KB Output is correct
63 Correct 11 ms 23760 KB Output is correct
64 Correct 10 ms 23760 KB Output is correct
65 Correct 15 ms 23784 KB Output is correct
66 Correct 22 ms 25280 KB Output is correct
67 Correct 91 ms 42308 KB Output is correct
68 Correct 88 ms 40008 KB Output is correct
69 Correct 92 ms 39496 KB Output is correct
70 Correct 11 ms 23872 KB Output is correct
71 Correct 72 ms 39684 KB Output is correct
72 Correct 75 ms 40120 KB Output is correct
73 Correct 72 ms 40136 KB Output is correct
74 Correct 104 ms 40412 KB Output is correct
75 Correct 69 ms 38752 KB Output is correct
76 Correct 67 ms 38332 KB Output is correct
77 Correct 74 ms 39712 KB Output is correct
78 Correct 1773 ms 133052 KB Output is correct
79 Correct 1844 ms 127888 KB Output is correct
80 Correct 1839 ms 130240 KB Output is correct
81 Correct 1630 ms 135944 KB Output is correct
82 Correct 1726 ms 134848 KB Output is correct
83 Correct 1555 ms 128664 KB Output is correct
84 Correct 1514 ms 128652 KB Output is correct
85 Correct 1526 ms 128572 KB Output is correct
86 Correct 1719 ms 134596 KB Output is correct
87 Correct 1758 ms 134688 KB Output is correct
88 Correct 1809 ms 137308 KB Output is correct
89 Correct 1797 ms 132000 KB Output is correct
90 Correct 1752 ms 134644 KB Output is correct
91 Correct 10 ms 23760 KB Output is correct
92 Correct 11 ms 23760 KB Output is correct
93 Correct 14 ms 23760 KB Output is correct
94 Correct 21 ms 25232 KB Output is correct
95 Correct 83 ms 42268 KB Output is correct
96 Correct 79 ms 39908 KB Output is correct
97 Correct 82 ms 39512 KB Output is correct
98 Correct 11 ms 23888 KB Output is correct
99 Correct 71 ms 39676 KB Output is correct
100 Correct 91 ms 40120 KB Output is correct
101 Correct 84 ms 40152 KB Output is correct
102 Correct 74 ms 40324 KB Output is correct
103 Correct 74 ms 38836 KB Output is correct
104 Correct 70 ms 38312 KB Output is correct
105 Correct 75 ms 39612 KB Output is correct
106 Correct 1760 ms 135156 KB Output is correct
107 Correct 1606 ms 139876 KB Output is correct
108 Correct 1560 ms 136252 KB Output is correct
109 Correct 1237 ms 140860 KB Output is correct
110 Correct 1481 ms 128608 KB Output is correct
111 Correct 1586 ms 128856 KB Output is correct
112 Correct 1761 ms 137684 KB Output is correct
113 Correct 1658 ms 133252 KB Output is correct
114 Correct 1822 ms 127868 KB Output is correct
115 Correct 1832 ms 130020 KB Output is correct
116 Correct 1535 ms 135776 KB Output is correct
117 Correct 1651 ms 134732 KB Output is correct
118 Correct 1444 ms 128876 KB Output is correct
119 Correct 1456 ms 128824 KB Output is correct
120 Correct 1446 ms 128648 KB Output is correct
121 Correct 1658 ms 134612 KB Output is correct
122 Correct 1651 ms 134760 KB Output is correct
123 Correct 1697 ms 137264 KB Output is correct
124 Correct 1752 ms 132076 KB Output is correct
125 Correct 1636 ms 134688 KB Output is correct
126 Correct 1664 ms 133008 KB Output is correct
127 Correct 1511 ms 135892 KB Output is correct
128 Correct 1627 ms 135068 KB Output is correct
129 Correct 1479 ms 131432 KB Output is correct
130 Correct 1646 ms 135100 KB Output is correct
131 Correct 1750 ms 132056 KB Output is correct
132 Correct 1667 ms 134760 KB Output is correct
133 Correct 10 ms 23760 KB Output is correct
134 Correct 12 ms 23788 KB Output is correct
135 Correct 15 ms 23776 KB Output is correct
136 Correct 22 ms 25284 KB Output is correct
137 Correct 79 ms 42296 KB Output is correct
138 Correct 78 ms 40008 KB Output is correct
139 Correct 71 ms 39452 KB Output is correct
140 Correct 11 ms 23812 KB Output is correct
141 Correct 73 ms 39744 KB Output is correct
142 Correct 76 ms 40136 KB Output is correct
143 Correct 76 ms 40160 KB Output is correct
144 Correct 74 ms 40300 KB Output is correct
145 Correct 69 ms 38728 KB Output is correct
146 Correct 68 ms 38216 KB Output is correct
147 Correct 77 ms 39724 KB Output is correct
148 Correct 1651 ms 135176 KB Output is correct
149 Correct 1574 ms 139964 KB Output is correct
150 Correct 1427 ms 136392 KB Output is correct
151 Correct 1121 ms 141052 KB Output is correct
152 Correct 1460 ms 128540 KB Output is correct
153 Correct 1466 ms 128944 KB Output is correct
154 Correct 1762 ms 137828 KB Output is correct
155 Correct 1922 ms 155992 KB Output is correct
156 Correct 2079 ms 176276 KB Output is correct
157 Correct 1779 ms 157244 KB Output is correct
158 Correct 1086 ms 133844 KB Output is correct
159 Correct 1828 ms 153528 KB Output is correct
160 Correct 1717 ms 140360 KB Output is correct
161 Correct 1662 ms 132868 KB Output is correct
162 Correct 1799 ms 127964 KB Output is correct
163 Correct 1773 ms 130072 KB Output is correct
164 Correct 1532 ms 135792 KB Output is correct
165 Correct 1653 ms 134752 KB Output is correct
166 Correct 1487 ms 128748 KB Output is correct
167 Correct 1509 ms 128528 KB Output is correct
168 Correct 1515 ms 128136 KB Output is correct
169 Correct 1667 ms 134260 KB Output is correct
170 Correct 1746 ms 134340 KB Output is correct
171 Correct 1684 ms 136784 KB Output is correct
172 Correct 1765 ms 131496 KB Output is correct
173 Correct 1656 ms 134252 KB Output is correct
174 Correct 1651 ms 132428 KB Output is correct
175 Correct 1585 ms 135208 KB Output is correct
176 Correct 1647 ms 134596 KB Output is correct
177 Correct 1487 ms 130960 KB Output is correct
178 Correct 1648 ms 134572 KB Output is correct
179 Correct 1761 ms 131584 KB Output is correct
180 Correct 1671 ms 134256 KB Output is correct
181 Correct 1728 ms 133208 KB Output is correct
182 Correct 1657 ms 137796 KB Output is correct
183 Correct 2113 ms 158320 KB Output is correct
184 Correct 1810 ms 149844 KB Output is correct
185 Correct 1956 ms 149624 KB Output is correct
186 Correct 1930 ms 132716 KB Output is correct
187 Correct 1497 ms 130112 KB Output is correct