oj.uz

Submission #1074298

# Submission time Handle Problem Language Result Execution time Memory
1074298 2024-08-25T09:30:42 Z Zanite Board Game (JOI24_boardgame) C++17
100 / 100
 3330 ms 124008 KB 
// こんな僕等がお互い蹴落として
// まで掴んだ物は何ですか
// 僕は　僕を愛してあげたい
// 
// こんなことなら生まれてこなけりゃって
// 全部嫌になってくけれど
// 絶えず　脈打つこれは何だろう
// 
// 何だろう...

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

// Pragmas
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

// Namespaces
using namespace std;
using namespace __gnu_pbds;

// Data types
using si  = short int;
using ll  = long long;
using ull = unsigned long long;
using lll = __int128;
using ld  = long double;

// Pairs
using pii  = pair<int, int>;
using psi  = pair<si, si>;
using pll  = pair<ll, ll>;
using plll = pair<lll, lll>;
using pld  = pair<ld, ld>;
#define fi first
#define se second

// PBDS
template<typename Z>
using ordered_set = tree<Z, null_type, less<Z>, rb_tree_tag, tree_order_statistics_node_update>;

// Various outputs and debug
template<typename Z, typename = void> struct is_iterable : false_type {};
template<typename Z> struct is_iterable<Z, void_t<decltype(begin(declval<Z>())),decltype(end(declval<Z>()))>> : true_type {};
template<typename Z> typename enable_if<is_iterable<Z>::value&&!is_same<Z, string>::value,ostream&>::type operator<<(ostream &os, const Z &v);

template<typename Y, typename Z> ostream& operator<<(ostream &os, const pair<Y, Z> &p) {
   return os << "(" << p.fi << ", " << p.se << ")";
}
template<class TupType, size_t... I> void printTuple(ostream& os, const TupType& _tup, index_sequence<I...>) {
   os << "(";
   (..., (os << (I == 0? "" : ", ") << get<I>(_tup)));
   os << ")";
}
template<class... Z> ostream& operator<<(ostream& os, const tuple<Z...>& _tup) {
   printTuple(os, _tup, make_index_sequence<sizeof...(Z)>());
   return os;
}
template<typename Z> typename enable_if<is_iterable<Z>::value&&!is_same<Z, string>::value,ostream&>::type operator<<(ostream &os, const Z &v) {
   os << "["; 
   for (auto it = v.begin(); it != v.end();) { os << *it; if (++it != v.end()) os << ", "; }
   return os << "]";
}

#define debug(...)   logger(cout, #__VA_ARGS__, __VA_ARGS__)
#define debugV(v, x)  vlogger(cout, #v, x, v[x]);
#define rrebug(...)   logger(cerr, #__VA_ARGS__, __VA_ARGS__)
#define rrebugV(v, x) vlogger(cerr, #v, x, v[x]);
template <typename... Args>
void logger(ostream& os, string vars, Args &&...values) {
   os << vars << " = "; string delim = "";
   (..., (os << delim << values, delim = ", "));
   os << "\n";
}
template<class Y, class Z>
void vlogger(ostream& os, string var, Y idx, Z val) {
   os << var << "[" << idx << "] = " << val << "\n";
}

// Various macros
#define All(x)         x.begin(), x.end()
#define Sort(x)         sort(All(x))
#define Reverse(x)      reverse(All(x))
#define Uniqueify(x)     Sort(x); x.erase(unique(All(x)), x.end())
#define RandomSeed      chrono::steady_clock::now().time_since_epoch().count()
#define MultipleTestcases int _tc; cin >> _tc; for (int _cur_tc = 1; _cur_tc <= _tc; _cur_tc++)

// Chmin & chmax
template<typename Z> bool chmin(Z &a, Z b) { return (b < a) ? a = b, true : false; }
template<typename Z> bool chmax(Z &a, Z b) { return (b > a) ? a = b, true : false; }
 
// Modular arithmetic
template<int MOD>
class ModInt {
  public:
   int v;
   ModInt() : v(0) {}
   ModInt(long long _v) {
      v = int((-MOD < _v && _v < MOD) ? (_v) : (_v % MOD));
      if (v < 0) v += MOD;
   }
 
   friend bool operator==(const ModInt &a, const ModInt &b) { return a.v == b.v; }
   friend bool operator!=(const ModInt &a, const ModInt &b) { return a.v != b.v; }
   friend bool operator< (const ModInt &a, const ModInt &b) { return a.v <  b.v; }
   friend bool operator<=(const ModInt &a, const ModInt &b) { return a.v <= b.v; }
   friend bool operator> (const ModInt &a, const ModInt &b) { return a.v >  b.v; }
   friend bool operator>=(const ModInt &a, const ModInt &b) { return a.v >= b.v; }
 
   ModInt &operator+=(const ModInt &a) { if ((v += a.v) >= MOD) v -= MOD; return *this; }
   ModInt &operator-=(const ModInt &a) { if ((v -= a.v) < 0) v += MOD; return *this; }
   ModInt &operator*=(const ModInt &a) { v = 1ll * v * a.v % MOD; return *this; }
   ModInt &operator/=(const ModInt &a) { return (*this) *= inverse(a); }
 
   friend ModInt pow(ModInt a, long long x) {
      ModInt res = 1;
      for (; x; x /= 2, a *= a) if (x & 1) res *= a;
      return res;
   }
   friend ModInt inverse(ModInt a) { return pow(a, MOD - 2); }
 
   ModInt operator+ () const { return ModInt( v); }
   ModInt operator- () const { return ModInt(-v); }
   ModInt operator++() const { return *this += 1; }
   ModInt operator--() const { return *this -= 1; }
 
   friend ModInt operator+(ModInt a, const ModInt &b) { return a += b; }
   friend ModInt operator-(ModInt a, const ModInt &b) { return a -= b; }
   friend ModInt operator*(ModInt a, const ModInt &b) { return a *= b; }
   friend ModInt operator/(ModInt a, const ModInt &b) { return a /= b; }
 
   friend istream &operator>>(istream &is, ModInt &v) { return is >> v.v; }
   friend ostream &operator<<(ostream &os, const ModInt &v) { return os << v.v; }
};
const int ModA = 998244353;
const int ModC = 1e9 + 7;
using MintA   = ModInt<ModA>;
using MintC   = ModInt<ModC>;

// Other constants
const ll INF  = 1e18;
const ll iINF = 1e9;
const ld EPS  = 1e-9;
const ld iEPS = 1e-6;

const int maxN  = 50'023;
const int THRES = 250;

int N, M, K;
vector<int> board[maxN];
bool state[maxN];
int st_pos[maxN];

ll dist_single[maxN], dist_double[maxN];
vector<pll> adj_single[maxN], adj_double[maxN];

ll total_cost[maxN];
ll tmp_dist[2][maxN], ans[maxN];

int min_stops[maxN];
ll fin_dist[THRES][maxN];
bool fin_vis[THRES][maxN];

void dijkstra(ll* dist, vector<pll> *adj) {
   vector<bool> vis(N + 1, false);
   priority_queue<pll, vector<pll>, greater<pll>> pyqe;
   for (int i = 1; i <= N; i++) {
      pyqe.push({dist[i], i});
   }

   while (!pyqe.empty()) {
      int cur = pyqe.top().se; pyqe.pop();
      if (vis[cur]) continue;

      vis[cur] = true;
      for (auto [nxt, w] : adj[cur]) {
         if (dist[nxt] > dist[cur] + w) {
            dist[nxt] = dist[cur] + w;
            pyqe.push({dist[nxt], nxt});
         }
      }
   }
}

void linear_dijkstra(ll m, ll c) {
   // {dist, gone at least once to stop, vertex}
   using State = tuple<ll, int, int>;

   for (int i = 1; i <= N; i++) {
      tmp_dist[0][i] = tmp_dist[1][i] = INF;
   }

   vector vis(2, vector(N + 1, false));
   priority_queue<State, vector<State>, greater<State>> pyqe;
   tmp_dist[0][st_pos[1]] = c;
   pyqe.push({c, 0, st_pos[1]});

   while (!pyqe.empty()) {
      auto [_, cs, cv] = pyqe.top(); pyqe.pop();
      if (vis[cs][cv]) continue;

      vis[cs][cv] = true;
      // cout << make_pair(cs, cv) << ": " << _ << "\n";
      for (auto nxt : board[cv]) {
         bool stop_state = (state[cv] && cv != st_pos[1]);
         ll w = (stop_state ? m : 0ll) + 1ll;
         int ns = cs | stop_state;
         if (tmp_dist[ns][nxt] > tmp_dist[cs][cv] + w) {
            tmp_dist[ns][nxt] = tmp_dist[cs][cv] + w;
            pyqe.push({tmp_dist[ns][nxt], ns, nxt});
         }
      }
   }

   for (int i = 1; i <= N; i++) {
      chmin(ans[i], tmp_dist[1][i]);
   }

   // debug(m, c, s);
   // for (int i = 1; i <= N; i++) {
   //    if (tmp_dist[1][i] >= INF) cout << "- ";
   //    else cout << tmp_dist[1][i] << " ";
   // }
   // cout << "\n\n";
}

void solve_reachable() {
   for (int i = 1; i <= N; i++) ans[i] = INF;
   ans[st_pos[1]] = 0;

   vector<bool> vis(N + 1, false);
   queue<int> q;
   for (int i = 1; i <= N; i++) q.push(st_pos[1]);

   while (!q.empty()) {
      int cur = q.front(); q.pop();
      if (vis[cur]) continue;

      vis[cur] = true;
      bool stop_state = (state[cur] && cur != st_pos[1]);
      if (stop_state) continue;
      for (auto nxt : board[cur]) {
         if (ans[nxt] > ans[cur] + 1) {
            ans[nxt] = ans[cur] + 1;
            q.push(nxt);
         }
      }
   }
}

void solve_small_k() {
   vector<pll> lines;
   for (int i = 2; i <= N; i++) {
      ll m = total_cost[i] - total_cost[i-1];
      ll c = total_cost[i] - (ll)i * m;
      lines.push_back({m, c});
   }
   Uniqueify(lines);
   // debug(lines);

   for (auto [m, c] : lines) linear_dijkstra(m, c);
}

void solve_large_k() {
   // get minimum stops needed to get to each node
   {
      for (int i = 1; i <= N; i++) min_stops[i] = iINF;
      min_stops[st_pos[1]] = 0;
      deque<int> dq;
      dq.push_back(st_pos[1]);

      vector<bool> vis(N+1, false);
      while (!dq.empty()) {
         int cur = dq.front(); dq.pop_front();
         if (vis[cur]) continue;

         vis[cur] = true;
         for (auto nxt : board[cur]) {
            int w = (state[cur] && cur != st_pos[1]);
            if (min_stops[nxt] > min_stops[cur] + w) {
               min_stops[nxt] = min_stops[cur] + w;
               if (w) dq.push_back(nxt);
               else dq.push_front(nxt);
            }
         }
      }
   }
   
   // Dijkstra with extra states
   {
      for (int ad = 0; ad < THRES; ad++) {
         for (int i = 1; i <= N; i++) fin_dist[ad][i] = INF;
      }
      queue<pii> q;
      q.push({0, st_pos[1]});
      fin_dist[0][st_pos[1]] = 0;

      while (!q.empty()) {
         auto [ad, cur] = q.front(); q.pop();
         if (fin_vis[ad][cur]) continue;

         fin_vis[ad][cur] = true;
         for (auto nxt : board[cur]) {
            bool stop_state = (state[cur] && cur != st_pos[1]);
            int nxt_ad = ad + min_stops[cur] - min_stops[nxt] + stop_state;
            if (0 <= nxt_ad && nxt_ad < THRES) {
               if (fin_dist[nxt_ad][nxt] > fin_dist[ad][cur] + 1) {
                  fin_dist[nxt_ad][nxt] = fin_dist[ad][cur] + 1;
                  q.push({nxt_ad, nxt});
               }
            }
         }
      }
   }

   for (int i = 1; i <= N; i++) {
      ans[i] = INF;
      for (int ad = 0; ad < THRES; ad++) {
         int act = ad + min_stops[i];
         if (act > N) break;
         // if (fin_dist[ad][i] + total_cost[act] < 0) {
         //    debug(ad, i, fin_dist[ad][i], total_cost[act]);
         //    exit(0);
         // }
         // debug(i, act, fin_dist[ad][i], total_cost[act]);
         chmin(ans[i], fin_dist[ad][i] + total_cost[act]);
      }
   }
}

void solve() {
   // compute distances to single and double stop nodes
   for (int i = 1; i <= N; i++) dist_single[i] = dist_double[i] = INF;

   for (int i = 1; i <= N; i++) {
      for (auto j : board[i]) {
         adj_single[i].push_back({j, 1});
         adj_double[i].push_back({j, !state[i]});
      }
      if (state[i]) {
         dist_single[i] = 0;
         for (auto j : board[i]) {
            if (state[j]) dist_double[i] = dist_double[j] = 0;
         }
      }
   }

   dijkstra(dist_single, adj_single);
   dijkstra(dist_double, adj_double);

   for (int i = 1; i <= N; i++) {
      if (dist_single[i] == 0) {
         dist_single[i] = 2;
      }
   }

   for (int i = 2; i <= K; i++) {
      ll c_single = dist_single[st_pos[i]] - 2;
      ll c_double = dist_double[st_pos[i]];

      // binary search switching position from single to double
      for (int j = 1; j <= N; j++) {
         total_cost[j] += min(
            2ll * j + c_single,
            1ll * j + c_double
         );
         chmin(total_cost[j], INF);
      }
   }

   // for (int i = 1; i <= N; i++) debugV(total_cost, i);

   // solve_small_k();
   // solve_large_k();

   if (K <= THRES) solve_small_k();
   else solve_large_k();

   for (int i = 1; i <= N; i++) {
      printf("%lld\n", ans[i]);
   }
}

int main() {
   scanf("%d %d %d", &N, &M, &K);
   for (int u, v, i = 1; i <= M; i++) {
      scanf("%d %d", &u, &v);
      board[u].push_back(v);
      board[v].push_back(u);
   }
   for (int i = 1; i <= N; i++) {
      char buf;
      scanf(" %c", &buf);
      state[i] = (buf == '1');
   }
   for (int i = 1; i <= K; i++) scanf("%d", &st_pos[i]);

   solve_reachable();
   solve();
}

// dibisakan

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:387:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  387 |    scanf("%d %d %d", &N, &M, &K);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:389:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  389 |       scanf("%d %d", &u, &v);
      |       ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:395:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  395 |       scanf(" %c", &buf);
      |       ~~~~~^~~~~~~~~~~~~
Main.cpp:398:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  398 |    for (int i = 1; i <= K; i++) scanf("%d", &st_pos[i]);
      |                                 ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 11608 KB Output is correct
2 Correct 814 ms 69532 KB Output is correct
3 Correct 2140 ms 111716 KB Output is correct
4 Correct 43 ms 15352 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 13396 KB Output is correct
2 Correct 1214 ms 77832 KB Output is correct
3 Correct 64 ms 15400 KB Output is correct
4 Correct 49 ms 15396 KB Output is correct
5 Correct 2517 ms 123740 KB Output is correct
6 Correct 62 ms 15408 KB Output is correct
7 Correct 43 ms 14152 KB Output is correct
8 Correct 48 ms 14996 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 13468 KB Output is correct
2 Correct 1222 ms 77948 KB Output is correct
3 Correct 1028 ms 123400 KB Output is correct
4 Correct 1361 ms 123532 KB Output is correct
5 Correct 2995 ms 123876 KB Output is correct
6 Correct 80 ms 15552 KB Output is correct
7 Correct 64 ms 15312 KB Output is correct
8 Correct 3048 ms 123852 KB Output is correct
9 Correct 346 ms 34748 KB Output is correct
10 Correct 22 ms 10716 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4444 KB Output is correct
2 Correct 6 ms 4700 KB Output is correct
3 Correct 43 ms 13396 KB Output is correct
4 Correct 9 ms 4700 KB Output is correct
5 Correct 5 ms 4696 KB Output is correct
6 Correct 4 ms 4444 KB Output is correct
7 Correct 23 ms 9860 KB Output is correct
8 Correct 38 ms 13324 KB Output is correct
9 Correct 6 ms 4444 KB Output is correct
10 Correct 4 ms 4532 KB Output is correct
11 Correct 7 ms 4444 KB Output is correct
12 Correct 7 ms 4440 KB Output is correct
13 Correct 4 ms 4444 KB Output is correct
14 Correct 5 ms 4444 KB Output is correct
15 Correct 11 ms 4676 KB Output is correct
16 Correct 19 ms 4676 KB Output is correct
17 Correct 56 ms 4668 KB Output is correct
18 Correct 5 ms 4444 KB Output is correct
19 Correct 9 ms 4664 KB Output is correct
20 Correct 9 ms 4444 KB Output is correct
21 Correct 57 ms 13448 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 15580 KB Output is correct
2 Correct 76 ms 15308 KB Output is correct
3 Correct 53 ms 15416 KB Output is correct
4 Correct 51 ms 15352 KB Output is correct
5 Correct 85 ms 15244 KB Output is correct
6 Correct 44 ms 14168 KB Output is correct
7 Correct 24 ms 11044 KB Output is correct
8 Correct 26 ms 9876 KB Output is correct
9 Correct 24 ms 9832 KB Output is correct
10 Correct 45 ms 14196 KB Output is correct
11 Correct 47 ms 14200 KB Output is correct
12 Correct 57 ms 15064 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 15580 KB Output is correct
2 Correct 76 ms 15308 KB Output is correct
3 Correct 53 ms 15416 KB Output is correct
4 Correct 51 ms 15352 KB Output is correct
5 Correct 85 ms 15244 KB Output is correct
6 Correct 44 ms 14168 KB Output is correct
7 Correct 24 ms 11044 KB Output is correct
8 Correct 26 ms 9876 KB Output is correct
9 Correct 24 ms 9832 KB Output is correct
10 Correct 45 ms 14196 KB Output is correct
11 Correct 47 ms 14200 KB Output is correct
12 Correct 57 ms 15064 KB Output is correct
13 Correct 57 ms 15448 KB Output is correct
14 Correct 75 ms 15312 KB Output is correct
15 Correct 175 ms 15432 KB Output is correct
16 Correct 145 ms 15364 KB Output is correct
17 Correct 42 ms 14152 KB Output is correct
18 Correct 148 ms 14204 KB Output is correct
19 Correct 144 ms 13764 KB Output is correct
20 Correct 72 ms 15332 KB Output is correct
21 Correct 42 ms 9956 KB Output is correct
22 Correct 38 ms 10412 KB Output is correct
23 Correct 38 ms 10408 KB Output is correct
24 Correct 45 ms 14340 KB Output is correct
25 Correct 50 ms 14884 KB Output is correct
26 Correct 54 ms 14936 KB Output is correct
27 Correct 50 ms 10408 KB Output is correct
28 Correct 169 ms 10408 KB Output is correct
29 Correct 296 ms 10396 KB Output is correct
30 Correct 58 ms 14884 KB Output is correct
31 Correct 304 ms 14904 KB Output is correct
32 Correct 531 ms 15048 KB Output is correct

Subtask #7
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4444 KB Output is correct
2 Correct 6 ms 4700 KB Output is correct
3 Correct 43 ms 13396 KB Output is correct
4 Correct 9 ms 4700 KB Output is correct
5 Correct 5 ms 4696 KB Output is correct
6 Correct 4 ms 4444 KB Output is correct
7 Correct 23 ms 9860 KB Output is correct
8 Correct 38 ms 13324 KB Output is correct
9 Correct 6 ms 4444 KB Output is correct
10 Correct 4 ms 4532 KB Output is correct
11 Correct 7 ms 4444 KB Output is correct
12 Correct 7 ms 4440 KB Output is correct
13 Correct 4 ms 4444 KB Output is correct
14 Correct 5 ms 4444 KB Output is correct
15 Correct 11 ms 4676 KB Output is correct
16 Correct 19 ms 4676 KB Output is correct
17 Correct 56 ms 4668 KB Output is correct
18 Correct 5 ms 4444 KB Output is correct
19 Correct 9 ms 4664 KB Output is correct
20 Correct 9 ms 4444 KB Output is correct
21 Correct 57 ms 13448 KB Output is correct
22 Correct 47 ms 10616 KB Output is correct
23 Correct 537 ms 77908 KB Output is correct
24 Correct 32 ms 10644 KB Output is correct
25 Correct 314 ms 10744 KB Output is correct
26 Correct 666 ms 77724 KB Output is correct
27 Correct 837 ms 77720 KB Output is correct
28 Correct 716 ms 77460 KB Output is correct
29 Correct 1351 ms 77748 KB Output is correct
30 Correct 50 ms 10596 KB Output is correct
31 Correct 1018 ms 77956 KB Output is correct
32 Correct 29 ms 9432 KB Output is correct
33 Correct 404 ms 54924 KB Output is correct
34 Correct 32 ms 10404 KB Output is correct
35 Correct 35 ms 10412 KB Output is correct
36 Correct 404 ms 77064 KB Output is correct
37 Correct 359 ms 76964 KB Output is correct
38 Correct 389 ms 76208 KB Output is correct
39 Correct 428 ms 10400 KB Output is correct
40 Correct 545 ms 10400 KB Output is correct
41 Correct 677 ms 77392 KB Output is correct
42 Correct 730 ms 77448 KB Output is correct
43 Correct 720 ms 77452 KB Output is correct
44 Correct 748 ms 77440 KB Output is correct
45 Correct 724 ms 77440 KB Output is correct
46 Correct 723 ms 77452 KB Output is correct
47 Correct 734 ms 77428 KB Output is correct
48 Correct 761 ms 78516 KB Output is correct
49 Correct 882 ms 78488 KB Output is correct
50 Correct 978 ms 78500 KB Output is correct
51 Correct 31 ms 10404 KB Output is correct
52 Correct 44 ms 10404 KB Output is correct
53 Correct 53 ms 10404 KB Output is correct
54 Correct 1422 ms 77840 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 11608 KB Output is correct
2 Correct 814 ms 69532 KB Output is correct
3 Correct 2140 ms 111716 KB Output is correct
4 Correct 43 ms 15352 KB Output is correct
5 Correct 35 ms 13396 KB Output is correct
6 Correct 1214 ms 77832 KB Output is correct
7 Correct 64 ms 15400 KB Output is correct
8 Correct 49 ms 15396 KB Output is correct
9 Correct 2517 ms 123740 KB Output is correct
10 Correct 62 ms 15408 KB Output is correct
11 Correct 43 ms 14152 KB Output is correct
12 Correct 48 ms 14996 KB Output is correct
13 Correct 38 ms 13468 KB Output is correct
14 Correct 1222 ms 77948 KB Output is correct
15 Correct 1028 ms 123400 KB Output is correct
16 Correct 1361 ms 123532 KB Output is correct
17 Correct 2995 ms 123876 KB Output is correct
18 Correct 80 ms 15552 KB Output is correct
19 Correct 64 ms 15312 KB Output is correct
20 Correct 3048 ms 123852 KB Output is correct
21 Correct 346 ms 34748 KB Output is correct
22 Correct 22 ms 10716 KB Output is correct
23 Correct 3 ms 4444 KB Output is correct
24 Correct 6 ms 4700 KB Output is correct
25 Correct 43 ms 13396 KB Output is correct
26 Correct 9 ms 4700 KB Output is correct
27 Correct 5 ms 4696 KB Output is correct
28 Correct 4 ms 4444 KB Output is correct
29 Correct 23 ms 9860 KB Output is correct
30 Correct 38 ms 13324 KB Output is correct
31 Correct 6 ms 4444 KB Output is correct
32 Correct 4 ms 4532 KB Output is correct
33 Correct 7 ms 4444 KB Output is correct
34 Correct 7 ms 4440 KB Output is correct
35 Correct 4 ms 4444 KB Output is correct
36 Correct 5 ms 4444 KB Output is correct
37 Correct 11 ms 4676 KB Output is correct
38 Correct 19 ms 4676 KB Output is correct
39 Correct 56 ms 4668 KB Output is correct
40 Correct 5 ms 4444 KB Output is correct
41 Correct 9 ms 4664 KB Output is correct
42 Correct 9 ms 4444 KB Output is correct
43 Correct 57 ms 13448 KB Output is correct
44 Correct 61 ms 15580 KB Output is correct
45 Correct 76 ms 15308 KB Output is correct
46 Correct 53 ms 15416 KB Output is correct
47 Correct 51 ms 15352 KB Output is correct
48 Correct 85 ms 15244 KB Output is correct
49 Correct 44 ms 14168 KB Output is correct
50 Correct 24 ms 11044 KB Output is correct
51 Correct 26 ms 9876 KB Output is correct
52 Correct 24 ms 9832 KB Output is correct
53 Correct 45 ms 14196 KB Output is correct
54 Correct 47 ms 14200 KB Output is correct
55 Correct 57 ms 15064 KB Output is correct
56 Correct 57 ms 15448 KB Output is correct
57 Correct 75 ms 15312 KB Output is correct
58 Correct 175 ms 15432 KB Output is correct
59 Correct 145 ms 15364 KB Output is correct
60 Correct 42 ms 14152 KB Output is correct
61 Correct 148 ms 14204 KB Output is correct
62 Correct 144 ms 13764 KB Output is correct
63 Correct 72 ms 15332 KB Output is correct
64 Correct 42 ms 9956 KB Output is correct
65 Correct 38 ms 10412 KB Output is correct
66 Correct 38 ms 10408 KB Output is correct
67 Correct 45 ms 14340 KB Output is correct
68 Correct 50 ms 14884 KB Output is correct
69 Correct 54 ms 14936 KB Output is correct
70 Correct 50 ms 10408 KB Output is correct
71 Correct 169 ms 10408 KB Output is correct
72 Correct 296 ms 10396 KB Output is correct
73 Correct 58 ms 14884 KB Output is correct
74 Correct 304 ms 14904 KB Output is correct
75 Correct 531 ms 15048 KB Output is correct
76 Correct 47 ms 10616 KB Output is correct
77 Correct 537 ms 77908 KB Output is correct
78 Correct 32 ms 10644 KB Output is correct
79 Correct 314 ms 10744 KB Output is correct
80 Correct 666 ms 77724 KB Output is correct
81 Correct 837 ms 77720 KB Output is correct
82 Correct 716 ms 77460 KB Output is correct
83 Correct 1351 ms 77748 KB Output is correct
84 Correct 50 ms 10596 KB Output is correct
85 Correct 1018 ms 77956 KB Output is correct
86 Correct 29 ms 9432 KB Output is correct
87 Correct 404 ms 54924 KB Output is correct
88 Correct 32 ms 10404 KB Output is correct
89 Correct 35 ms 10412 KB Output is correct
90 Correct 404 ms 77064 KB Output is correct
91 Correct 359 ms 76964 KB Output is correct
92 Correct 389 ms 76208 KB Output is correct
93 Correct 428 ms 10400 KB Output is correct
94 Correct 545 ms 10400 KB Output is correct
95 Correct 677 ms 77392 KB Output is correct
96 Correct 730 ms 77448 KB Output is correct
97 Correct 720 ms 77452 KB Output is correct
98 Correct 748 ms 77440 KB Output is correct
99 Correct 724 ms 77440 KB Output is correct
100 Correct 723 ms 77452 KB Output is correct
101 Correct 734 ms 77428 KB Output is correct
102 Correct 761 ms 78516 KB Output is correct
103 Correct 882 ms 78488 KB Output is correct
104 Correct 978 ms 78500 KB Output is correct
105 Correct 31 ms 10404 KB Output is correct
106 Correct 44 ms 10404 KB Output is correct
107 Correct 53 ms 10404 KB Output is correct
108 Correct 1422 ms 77840 KB Output is correct
109 Correct 1029 ms 123624 KB Output is correct
110 Correct 1041 ms 123616 KB Output is correct
111 Correct 56 ms 15488 KB Output is correct
112 Correct 389 ms 15284 KB Output is correct
113 Correct 1221 ms 123520 KB Output is correct
114 Correct 979 ms 123636 KB Output is correct
115 Correct 68 ms 15372 KB Output is correct
116 Correct 85 ms 15320 KB Output is correct
117 Correct 777 ms 102964 KB Output is correct
118 Correct 233 ms 34352 KB Output is correct
119 Correct 253 ms 34356 KB Output is correct
120 Correct 730 ms 97964 KB Output is correct
121 Correct 3298 ms 124008 KB Output is correct
122 Correct 55 ms 14880 KB Output is correct
123 Correct 714 ms 123296 KB Output is correct
124 Correct 619 ms 123180 KB Output is correct
125 Correct 622 ms 123236 KB Output is correct
126 Correct 754 ms 14880 KB Output is correct
127 Correct 956 ms 14972 KB Output is correct
128 Correct 1366 ms 123164 KB Output is correct
129 Correct 1327 ms 123172 KB Output is correct
130 Correct 1419 ms 123096 KB Output is correct
131 Correct 1447 ms 123144 KB Output is correct
132 Correct 1325 ms 123172 KB Output is correct
133 Correct 1381 ms 123176 KB Output is correct
134 Correct 1373 ms 123176 KB Output is correct
135 Correct 1451 ms 123072 KB Output is correct
136 Correct 1414 ms 123196 KB Output is correct
137 Correct 1449 ms 123204 KB Output is correct
138 Correct 1690 ms 123184 KB Output is correct
139 Correct 1994 ms 123352 KB Output is correct
140 Correct 54 ms 14832 KB Output is correct
141 Correct 71 ms 14832 KB Output is correct
142 Correct 1285 ms 123172 KB Output is correct
143 Correct 3330 ms 123660 KB Output is correct