oj.uz

Submission #473940

# Submission time Handle Problem Language Result Execution time Memory
473940 2021-09-16T12:36:37 Z model_code Wells (CEOI21_wells) C++17
100 / 100
 3790 ms 256344 KB 
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <vector>
#include <cstring>
#include <iostream>
#include <cmath>
#include <string>

#define FOR(i, a, b) for (int i=(a); i<(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define TRACE(x) cerr << #x << " = " << x << endl
#define _ << " _ " <<
#define X first
#define Y second

using namespace std;

typedef pair<int, int> P;
typedef long long ll;

const int MAX = 3000050, MOD = 1e9 + 7;

int add(int a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
  return a;
}

int sub(int a, int b) {
  a -= b;
  if (a < 0) a += MOD;
  return a;
}

int mul(int a, int b) {
  return (int) (((ll) a * b) % MOD);
}

int inverse(int a) {
  int pot = MOD-2, ret = 1;
  for (; pot; pot /= 2, a = mul(a, a))
    if (pot & 1)
      ret = mul(ret, a);

  return ret;
}

vector <int> V[MAX];
int n, k;

void load() {
  scanf("%d%d", &n, &k);
  REP(i, n-1) {
    int a, b;
    scanf("%d%d", &a, &b); a--; b--;
    V[a].push_back(b);
    V[b].push_back(a);
  }
}

void dfs_dist(int node, int pr, vector<int> &dist) {
  if (pr != -1) dist[node] = dist[pr] + 1;
  else dist[node] = 0;

  for (auto it : V[node]) if (it != pr) dfs_dist(it, node, dist);
}

bool dfs_diam(int node, int pr, int fin, vector<int> &D) {
  D.push_back(node);
  if (node == fin) return true;

  for (auto it : V[node])
    if (it != pr && dfs_diam(it, node, fin, D)) return true;

  D.pop_back();
  return false;
}

vector <int> get_diam() {
  vector <int> dist(n);

  dfs_dist(0, -1, dist);
  int p1 = 0;
  REP(i, n) if (dist[i] > dist[p1]) p1 = i;

  dfs_dist(p1, -1, dist);
  int p2 = p1;
  REP(i, n) if (dist[i] > dist[p2]) p2 = i;

  vector <int> D;
  dfs_diam(p1, -1, p2, D);

  return D;
}

int dist_to_root[MAX], ind_diam_root[MAX], height[MAX];
bool on_diam[MAX];

int dfs_from_root(int node, int pr, int ind_diam_rt, int dst) {
  ind_diam_root[node] = ind_diam_rt;
  dist_to_root[node] = dst;

  int mx_dep = 0;
  for (auto it : V[node])
    if (it != pr && !on_diam[it])
      mx_dep = max(mx_dep, 1 + dfs_from_root(it, node, ind_diam_rt, dst + 1));

  return height[node] = mx_dep;
}

bool forb[MAX];
vector <int> not_forb;
bool irrelevant[MAX];

int get_ways(int node, int pr, int depth_left) {
  assert(depth_left >= 0);
  if (depth_left == 0) return 1;
  if (irrelevant[node]) return 1;

  int tmp = 1;
  for (auto it : V[node])
    if (!on_diam[it] && it != pr)
      tmp = mul(tmp, get_ways(it, node, depth_left-1));

  return add(tmp, 1);
}

int no_irrel=0;
int pref_mult[MAX];
int dsize;

void update_interval(int a, int b, int val) { //[, )
  assert(a >= 0 && a < k && b >= 0 && b <= k);
  if (a <= b) {
    pref_mult[a] = mul(pref_mult[a], val);
    pref_mult[b] = mul(pref_mult[b], inverse(val));
  }
  else {
    pref_mult[0] = mul(pref_mult[0], val);
    pref_mult[b] = mul(pref_mult[0], inverse(val));
    pref_mult[a] = mul(pref_mult[a], val);
  }
}

void dfs_ways(int node, int pr) {
  if (!on_diam[node]) {
    int d_l = dist_to_root[node] + ind_diam_root[node];
    int d_r = dist_to_root[node] + dsize-1 - ind_diam_root[node];
    int mx_l = d_l + height[node];
    int mx_r = d_r + height[node];

    if (mx_l + 1 >= k && mx_r + 1 < k) {
      if (d_l < k) {
        int ways = get_ways(node, pr, k - d_l - 1);
        update_interval(ind_diam_root[node]+1, k, ways);
        //TRACE(ind_diam_root[node]+1 _ k _ ways);
      }
      return;
    }
    else if (mx_l + 1 < k && mx_r + 1 >= k) {
      if (d_r < k) {
        int ways = get_ways(node, pr, k - d_r - 1);
        update_interval(dsize % k, ind_diam_root[node], ways);
        //TRACE(dsize % k _ ind_diam_root[node] _ ways);
      }
      return;
    }
    else if (mx_l + 1 >= k && mx_r + 1 >= k) {

      int dep1 = -2 * MAX, dep2 = -2 * MAX;
      for (auto ch : V[node]) {
        if (!on_diam[ch] && ch != pr) {
          if (height[ch] > dep1) {
            dep2 = dep1;
            dep1 = height[ch];
          }
          else dep2 = max(dep2, height[ch]);
        }
      }

      if (1+dep1 + 1+dep2 + 1 >= k) {
        assert(not_forb.size() <= 2);
        int my_res = d_l % k;

        for (auto residue : not_forb) {
          if (my_res == residue) continue;
          int to_next = (k - my_res + residue) % k;

          //TRACE(node _ to_next _ dep1 _ dep2);
          //TRACE(forb[0] _ forb[1]);
          if (to_next <= 1 + dep2 && 2 * to_next + 1 <= k) forb[residue] = true; //two reds
          if (min(1+dep1, to_next-1) + min(1+dep2, to_next-1) + 1 >= k) forb[residue] = true; //no reds


          //TRACE("AFTER" _ forb[0] _ forb[1]);
        }
      }
    }
  }

  for (auto ch : V[node])
    if (!on_diam[ch] && ch != pr)
      dfs_ways(ch, node);
}

int main()
{
  load();

  vector <int> D = get_diam();
  for (auto it : D) on_diam[it] = true;

  dsize = (int) D.size();
  REP(i, dsize)
    dfs_from_root(D[i], -1, i, 0);

//  REP(i, dsize) TRACE(i _ D[i]);

  if (dsize < k) {
    printf("YES\n");
    int cnt=1;
    REP(i, n) cnt = mul(cnt, 2);
    printf("%d\n", cnt);
    return 0;
  }

  REP(i, MAX) pref_mult[i] = 1;


  REP(node, n) {
    if (on_diam[node]) continue;

    int d_l = dist_to_root[node] + ind_diam_root[node];
    int d_r = dist_to_root[node] + dsize-1 - ind_diam_root[node];
    int mx_l = d_l + height[node];
    int mx_r = d_r + height[node];

    if (mx_l+1 < k && mx_r+1 < k) {
      no_irrel++;
      irrelevant[node] = true;
    }
    else if (mx_l+1 >= k && mx_r+1 >= k) {
      int colored_l = d_l % k;
      int colored_r = ((ind_diam_root[node] - dist_to_root[node]) % k + k) % k;

      if (colored_l != colored_r)
        forb[colored_l] = forb[colored_r] = true;
    }
  }

  REP(i, k)
    if (!forb[i]) not_forb.push_back(i);

//  REP(i, k) TRACE("ASDASD" _ i _ forb[i]);

  for (auto it : D)
    dfs_ways(it, -1);

  bool can = false;
  REP(i, k) can |= !forb[i];

  printf("%s\n", (can ? "YES" : "NO"));
  int ways = 0;

  REP(i, k) {
    if (i) pref_mult[i] = mul(pref_mult[i], pref_mult[i-1]);
    if (!forb[i]) {
      ways = add(ways, pref_mult[i]);
      //TRACE(i _ pref_mult[i]);
    }

    //TRACE(i _ forb[i] _ pref_mult[i]);
  }

  //TRACE(no_irrel);
  REP(i, no_irrel) ways = mul(ways, 2);
  printf("%d\n", ways);

  return 0;
}

Compilation message

wells.cpp: In function 'void load()':
wells.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |   scanf("%d%d", &n, &k);
      |   ~~~~~^~~~~~~~~~~~~~~~
wells.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |     scanf("%d%d", &a, &b); a--; b--;
      |     ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 82416 KB Output is correct
2 Correct 47 ms 82584 KB Output is correct
3 Correct 47 ms 82500 KB Output is correct
4 Correct 47 ms 82436 KB Output is correct
5 Correct 48 ms 82500 KB Output is correct
6 Correct 47 ms 82420 KB Output is correct
7 Correct 55 ms 82488 KB Output is correct
8 Correct 48 ms 82448 KB Output is correct
9 Correct 49 ms 82468 KB Output is correct
10 Correct 48 ms 82496 KB Output is correct
11 Correct 49 ms 82496 KB Output is correct
12 Correct 42 ms 70732 KB Output is correct
13 Correct 47 ms 82500 KB Output is correct
14 Correct 48 ms 82420 KB Output is correct
15 Correct 50 ms 82528 KB Output is correct
16 Correct 50 ms 82528 KB Output is correct
17 Correct 48 ms 82500 KB Output is correct
18 Correct 49 ms 82500 KB Output is correct
19 Correct 52 ms 82468 KB Output is correct
20 Correct 51 ms 82436 KB Output is correct
21 Correct 51 ms 82500 KB Output is correct
22 Correct 50 ms 82416 KB Output is correct
23 Correct 53 ms 82496 KB Output is correct
24 Correct 51 ms 82460 KB Output is correct
25 Correct 51 ms 82532 KB Output is correct
26 Correct 48 ms 82552 KB Output is correct
27 Correct 52 ms 82508 KB Output is correct
28 Correct 49 ms 82500 KB Output is correct
29 Correct 50 ms 82552 KB Output is correct
30 Correct 52 ms 82500 KB Output is correct
31 Correct 60 ms 82424 KB Output is correct
32 Correct 52 ms 82436 KB Output is correct
33 Correct 51 ms 82520 KB Output is correct
34 Correct 49 ms 82508 KB Output is correct
35 Correct 51 ms 82508 KB Output is correct
36 Correct 49 ms 82460 KB Output is correct
37 Correct 51 ms 82500 KB Output is correct
38 Correct 50 ms 82436 KB Output is correct
39 Correct 52 ms 82484 KB Output is correct
40 Correct 50 ms 82528 KB Output is correct
41 Correct 51 ms 82420 KB Output is correct
42 Correct 51 ms 82536 KB Output is correct
43 Correct 51 ms 82528 KB Output is correct
44 Correct 50 ms 82444 KB Output is correct
45 Correct 48 ms 82412 KB Output is correct
46 Correct 54 ms 82492 KB Output is correct
47 Correct 52 ms 82500 KB Output is correct
48 Correct 49 ms 82452 KB Output is correct
49 Correct 50 ms 82500 KB Output is correct
50 Correct 50 ms 82500 KB Output is correct
51 Correct 51 ms 82524 KB Output is correct
52 Correct 51 ms 82520 KB Output is correct
53 Correct 51 ms 82468 KB Output is correct
54 Correct 57 ms 82536 KB Output is correct
55 Correct 55 ms 82500 KB Output is correct
56 Correct 49 ms 82444 KB Output is correct
57 Correct 53 ms 82520 KB Output is correct
58 Correct 51 ms 82464 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 82416 KB Output is correct
2 Correct 47 ms 82584 KB Output is correct
3 Correct 47 ms 82500 KB Output is correct
4 Correct 47 ms 82436 KB Output is correct
5 Correct 48 ms 82500 KB Output is correct
6 Correct 47 ms 82420 KB Output is correct
7 Correct 55 ms 82488 KB Output is correct
8 Correct 48 ms 82448 KB Output is correct
9 Correct 49 ms 82468 KB Output is correct
10 Correct 48 ms 82496 KB Output is correct
11 Correct 49 ms 82496 KB Output is correct
12 Correct 42 ms 70732 KB Output is correct
13 Correct 47 ms 82500 KB Output is correct
14 Correct 48 ms 82420 KB Output is correct
15 Correct 50 ms 82528 KB Output is correct
16 Correct 50 ms 82528 KB Output is correct
17 Correct 48 ms 82500 KB Output is correct
18 Correct 49 ms 82500 KB Output is correct
19 Correct 52 ms 82468 KB Output is correct
20 Correct 51 ms 82436 KB Output is correct
21 Correct 51 ms 82500 KB Output is correct
22 Correct 50 ms 82416 KB Output is correct
23 Correct 53 ms 82496 KB Output is correct
24 Correct 51 ms 82460 KB Output is correct
25 Correct 51 ms 82532 KB Output is correct
26 Correct 48 ms 82552 KB Output is correct
27 Correct 52 ms 82508 KB Output is correct
28 Correct 49 ms 82500 KB Output is correct
29 Correct 50 ms 82552 KB Output is correct
30 Correct 52 ms 82500 KB Output is correct
31 Correct 60 ms 82424 KB Output is correct
32 Correct 52 ms 82436 KB Output is correct
33 Correct 51 ms 82520 KB Output is correct
34 Correct 49 ms 82508 KB Output is correct
35 Correct 51 ms 82508 KB Output is correct
36 Correct 49 ms 82460 KB Output is correct
37 Correct 51 ms 82500 KB Output is correct
38 Correct 50 ms 82436 KB Output is correct
39 Correct 52 ms 82484 KB Output is correct
40 Correct 50 ms 82528 KB Output is correct
41 Correct 51 ms 82420 KB Output is correct
42 Correct 51 ms 82536 KB Output is correct
43 Correct 51 ms 82528 KB Output is correct
44 Correct 50 ms 82444 KB Output is correct
45 Correct 48 ms 82412 KB Output is correct
46 Correct 54 ms 82492 KB Output is correct
47 Correct 52 ms 82500 KB Output is correct
48 Correct 49 ms 82452 KB Output is correct
49 Correct 50 ms 82500 KB Output is correct
50 Correct 50 ms 82500 KB Output is correct
51 Correct 51 ms 82524 KB Output is correct
52 Correct 51 ms 82520 KB Output is correct
53 Correct 51 ms 82468 KB Output is correct
54 Correct 57 ms 82536 KB Output is correct
55 Correct 55 ms 82500 KB Output is correct
56 Correct 49 ms 82444 KB Output is correct
57 Correct 53 ms 82520 KB Output is correct
58 Correct 51 ms 82464 KB Output is correct
59 Correct 49 ms 82440 KB Output is correct
60 Correct 51 ms 82764 KB Output is correct
61 Correct 51 ms 82748 KB Output is correct
62 Correct 52 ms 82764 KB Output is correct
63 Correct 59 ms 83092 KB Output is correct
64 Correct 57 ms 83392 KB Output is correct
65 Correct 56 ms 82944 KB Output is correct
66 Correct 55 ms 83020 KB Output is correct
67 Correct 55 ms 83448 KB Output is correct
68 Correct 53 ms 82800 KB Output is correct
69 Correct 51 ms 82628 KB Output is correct
70 Correct 51 ms 71304 KB Output is correct
71 Correct 53 ms 82720 KB Output is correct
72 Correct 53 ms 82756 KB Output is correct
73 Correct 62 ms 82884 KB Output is correct
74 Correct 54 ms 83268 KB Output is correct
75 Correct 58 ms 83028 KB Output is correct
76 Correct 58 ms 83080 KB Output is correct
77 Correct 55 ms 82756 KB Output is correct
78 Correct 60 ms 82708 KB Output is correct
79 Correct 53 ms 82700 KB Output is correct
80 Correct 55 ms 83136 KB Output is correct
81 Correct 56 ms 83148 KB Output is correct
82 Correct 59 ms 83012 KB Output is correct
83 Correct 57 ms 83232 KB Output is correct
84 Correct 57 ms 83068 KB Output is correct
85 Correct 55 ms 83216 KB Output is correct
86 Correct 56 ms 83104 KB Output is correct
87 Correct 57 ms 83216 KB Output is correct
88 Correct 57 ms 83140 KB Output is correct
89 Correct 60 ms 82980 KB Output is correct
90 Correct 51 ms 82752 KB Output is correct
91 Correct 55 ms 83140 KB Output is correct
92 Correct 54 ms 83260 KB Output is correct
93 Correct 58 ms 83272 KB Output is correct
94 Correct 60 ms 82904 KB Output is correct
95 Correct 58 ms 83012 KB Output is correct
96 Correct 56 ms 82792 KB Output is correct
97 Correct 52 ms 82944 KB Output is correct
98 Correct 54 ms 82844 KB Output is correct
99 Correct 53 ms 82884 KB Output is correct
100 Correct 56 ms 83216 KB Output is correct
101 Correct 56 ms 82992 KB Output is correct
102 Correct 59 ms 83224 KB Output is correct
103 Correct 53 ms 83140 KB Output is correct
104 Correct 56 ms 83144 KB Output is correct
105 Correct 56 ms 83240 KB Output is correct
106 Correct 56 ms 83080 KB Output is correct
107 Correct 55 ms 83268 KB Output is correct
108 Correct 67 ms 83032 KB Output is correct
109 Correct 60 ms 83016 KB Output is correct
110 Correct 55 ms 83196 KB Output is correct
111 Correct 55 ms 83040 KB Output is correct
112 Correct 55 ms 83196 KB Output is correct
113 Correct 57 ms 83160 KB Output is correct
114 Correct 56 ms 83176 KB Output is correct
115 Correct 56 ms 83012 KB Output is correct
116 Correct 58 ms 83332 KB Output is correct
117 Correct 59 ms 83036 KB Output is correct
118 Correct 56 ms 83244 KB Output is correct
119 Correct 55 ms 83012 KB Output is correct
120 Correct 57 ms 83232 KB Output is correct
121 Correct 63 ms 83196 KB Output is correct
122 Correct 60 ms 83224 KB Output is correct
123 Correct 58 ms 83156 KB Output is correct
124 Correct 56 ms 83256 KB Output is correct
125 Correct 56 ms 83108 KB Output is correct
126 Correct 56 ms 83004 KB Output is correct
127 Correct 57 ms 83388 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 82416 KB Output is correct
2 Correct 47 ms 82584 KB Output is correct
3 Correct 47 ms 82500 KB Output is correct
4 Correct 47 ms 82436 KB Output is correct
5 Correct 48 ms 82500 KB Output is correct
6 Correct 47 ms 82420 KB Output is correct
7 Correct 55 ms 82488 KB Output is correct
8 Correct 48 ms 82448 KB Output is correct
9 Correct 49 ms 82468 KB Output is correct
10 Correct 48 ms 82496 KB Output is correct
11 Correct 49 ms 82496 KB Output is correct
12 Correct 42 ms 70732 KB Output is correct
13 Correct 47 ms 82500 KB Output is correct
14 Correct 48 ms 82420 KB Output is correct
15 Correct 50 ms 82528 KB Output is correct
16 Correct 50 ms 82528 KB Output is correct
17 Correct 48 ms 82500 KB Output is correct
18 Correct 49 ms 82500 KB Output is correct
19 Correct 52 ms 82468 KB Output is correct
20 Correct 51 ms 82436 KB Output is correct
21 Correct 51 ms 82500 KB Output is correct
22 Correct 50 ms 82416 KB Output is correct
23 Correct 53 ms 82496 KB Output is correct
24 Correct 51 ms 82460 KB Output is correct
25 Correct 51 ms 82532 KB Output is correct
26 Correct 48 ms 82552 KB Output is correct
27 Correct 52 ms 82508 KB Output is correct
28 Correct 49 ms 82500 KB Output is correct
29 Correct 50 ms 82552 KB Output is correct
30 Correct 52 ms 82500 KB Output is correct
31 Correct 60 ms 82424 KB Output is correct
32 Correct 52 ms 82436 KB Output is correct
33 Correct 51 ms 82520 KB Output is correct
34 Correct 49 ms 82508 KB Output is correct
35 Correct 51 ms 82508 KB Output is correct
36 Correct 49 ms 82460 KB Output is correct
37 Correct 51 ms 82500 KB Output is correct
38 Correct 50 ms 82436 KB Output is correct
39 Correct 52 ms 82484 KB Output is correct
40 Correct 50 ms 82528 KB Output is correct
41 Correct 51 ms 82420 KB Output is correct
42 Correct 51 ms 82536 KB Output is correct
43 Correct 51 ms 82528 KB Output is correct
44 Correct 50 ms 82444 KB Output is correct
45 Correct 48 ms 82412 KB Output is correct
46 Correct 54 ms 82492 KB Output is correct
47 Correct 52 ms 82500 KB Output is correct
48 Correct 49 ms 82452 KB Output is correct
49 Correct 50 ms 82500 KB Output is correct
50 Correct 50 ms 82500 KB Output is correct
51 Correct 51 ms 82524 KB Output is correct
52 Correct 51 ms 82520 KB Output is correct
53 Correct 51 ms 82468 KB Output is correct
54 Correct 57 ms 82536 KB Output is correct
55 Correct 55 ms 82500 KB Output is correct
56 Correct 49 ms 82444 KB Output is correct
57 Correct 53 ms 82520 KB Output is correct
58 Correct 51 ms 82464 KB Output is correct
59 Correct 49 ms 82440 KB Output is correct
60 Correct 51 ms 82764 KB Output is correct
61 Correct 51 ms 82748 KB Output is correct
62 Correct 52 ms 82764 KB Output is correct
63 Correct 59 ms 83092 KB Output is correct
64 Correct 57 ms 83392 KB Output is correct
65 Correct 56 ms 82944 KB Output is correct
66 Correct 55 ms 83020 KB Output is correct
67 Correct 55 ms 83448 KB Output is correct
68 Correct 53 ms 82800 KB Output is correct
69 Correct 51 ms 82628 KB Output is correct
70 Correct 51 ms 71304 KB Output is correct
71 Correct 53 ms 82720 KB Output is correct
72 Correct 53 ms 82756 KB Output is correct
73 Correct 62 ms 82884 KB Output is correct
74 Correct 54 ms 83268 KB Output is correct
75 Correct 58 ms 83028 KB Output is correct
76 Correct 58 ms 83080 KB Output is correct
77 Correct 55 ms 82756 KB Output is correct
78 Correct 60 ms 82708 KB Output is correct
79 Correct 53 ms 82700 KB Output is correct
80 Correct 55 ms 83136 KB Output is correct
81 Correct 56 ms 83148 KB Output is correct
82 Correct 59 ms 83012 KB Output is correct
83 Correct 57 ms 83232 KB Output is correct
84 Correct 57 ms 83068 KB Output is correct
85 Correct 55 ms 83216 KB Output is correct
86 Correct 56 ms 83104 KB Output is correct
87 Correct 57 ms 83216 KB Output is correct
88 Correct 57 ms 83140 KB Output is correct
89 Correct 60 ms 82980 KB Output is correct
90 Correct 51 ms 82752 KB Output is correct
91 Correct 55 ms 83140 KB Output is correct
92 Correct 54 ms 83260 KB Output is correct
93 Correct 58 ms 83272 KB Output is correct
94 Correct 60 ms 82904 KB Output is correct
95 Correct 58 ms 83012 KB Output is correct
96 Correct 56 ms 82792 KB Output is correct
97 Correct 52 ms 82944 KB Output is correct
98 Correct 54 ms 82844 KB Output is correct
99 Correct 53 ms 82884 KB Output is correct
100 Correct 56 ms 83216 KB Output is correct
101 Correct 56 ms 82992 KB Output is correct
102 Correct 59 ms 83224 KB Output is correct
103 Correct 53 ms 83140 KB Output is correct
104 Correct 56 ms 83144 KB Output is correct
105 Correct 56 ms 83240 KB Output is correct
106 Correct 56 ms 83080 KB Output is correct
107 Correct 55 ms 83268 KB Output is correct
108 Correct 67 ms 83032 KB Output is correct
109 Correct 60 ms 83016 KB Output is correct
110 Correct 55 ms 83196 KB Output is correct
111 Correct 55 ms 83040 KB Output is correct
112 Correct 55 ms 83196 KB Output is correct
113 Correct 57 ms 83160 KB Output is correct
114 Correct 56 ms 83176 KB Output is correct
115 Correct 56 ms 83012 KB Output is correct
116 Correct 58 ms 83332 KB Output is correct
117 Correct 59 ms 83036 KB Output is correct
118 Correct 56 ms 83244 KB Output is correct
119 Correct 55 ms 83012 KB Output is correct
120 Correct 57 ms 83232 KB Output is correct
121 Correct 63 ms 83196 KB Output is correct
122 Correct 60 ms 83224 KB Output is correct
123 Correct 58 ms 83156 KB Output is correct
124 Correct 56 ms 83256 KB Output is correct
125 Correct 56 ms 83108 KB Output is correct
126 Correct 56 ms 83004 KB Output is correct
127 Correct 57 ms 83388 KB Output is correct
128 Correct 54 ms 82400 KB Output is correct
129 Correct 345 ms 92840 KB Output is correct
130 Correct 338 ms 100012 KB Output is correct
131 Correct 331 ms 102056 KB Output is correct
132 Correct 312 ms 91684 KB Output is correct
133 Correct 385 ms 96112 KB Output is correct
134 Correct 294 ms 96656 KB Output is correct
135 Correct 418 ms 91404 KB Output is correct
136 Correct 347 ms 94756 KB Output is correct
137 Correct 292 ms 95476 KB Output is correct
138 Correct 315 ms 101928 KB Output is correct
139 Correct 799 ms 109612 KB Output is correct
140 Correct 844 ms 120224 KB Output is correct
141 Correct 854 ms 111656 KB Output is correct
142 Correct 1006 ms 115504 KB Output is correct
143 Correct 991 ms 114572 KB Output is correct
144 Correct 954 ms 111252 KB Output is correct
145 Correct 995 ms 128028 KB Output is correct
146 Correct 643 ms 114908 KB Output is correct
147 Correct 787 ms 126932 KB Output is correct
148 Correct 1053 ms 104504 KB Output is correct
149 Correct 382 ms 93476 KB Output is correct
150 Correct 457 ms 92932 KB Output is correct
151 Correct 432 ms 96040 KB Output is correct
152 Correct 370 ms 92396 KB Output is correct
153 Correct 413 ms 92016 KB Output is correct
154 Correct 368 ms 91436 KB Output is correct
155 Correct 365 ms 95336 KB Output is correct
156 Correct 307 ms 96480 KB Output is correct
157 Correct 320 ms 93968 KB Output is correct
158 Correct 326 ms 95164 KB Output is correct
159 Correct 328 ms 99960 KB Output is correct
160 Correct 751 ms 108356 KB Output is correct
161 Correct 862 ms 120268 KB Output is correct
162 Correct 980 ms 126108 KB Output is correct
163 Correct 998 ms 119472 KB Output is correct
164 Correct 979 ms 124828 KB Output is correct
165 Correct 1028 ms 112944 KB Output is correct
166 Correct 872 ms 114140 KB Output is correct
167 Correct 997 ms 121420 KB Output is correct
168 Correct 764 ms 116920 KB Output is correct
169 Correct 663 ms 117624 KB Output is correct
170 Correct 571 ms 113284 KB Output is correct
171 Correct 1002 ms 104836 KB Output is correct
172 Correct 1038 ms 106788 KB Output is correct
173 Correct 886 ms 114944 KB Output is correct
174 Correct 922 ms 115888 KB Output is correct
175 Correct 905 ms 112068 KB Output is correct
176 Correct 905 ms 111624 KB Output is correct
177 Correct 841 ms 111752 KB Output is correct
178 Correct 963 ms 125652 KB Output is correct
179 Correct 697 ms 117612 KB Output is correct
180 Correct 663 ms 117536 KB Output is correct
181 Correct 701 ms 104092 KB Output is correct
182 Correct 940 ms 117212 KB Output is correct
183 Correct 905 ms 117960 KB Output is correct
184 Correct 809 ms 111428 KB Output is correct
185 Correct 870 ms 109172 KB Output is correct
186 Correct 764 ms 106708 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 82416 KB Output is correct
2 Correct 47 ms 82584 KB Output is correct
3 Correct 47 ms 82500 KB Output is correct
4 Correct 47 ms 82436 KB Output is correct
5 Correct 48 ms 82500 KB Output is correct
6 Correct 47 ms 82420 KB Output is correct
7 Correct 55 ms 82488 KB Output is correct
8 Correct 48 ms 82448 KB Output is correct
9 Correct 49 ms 82468 KB Output is correct
10 Correct 48 ms 82496 KB Output is correct
11 Correct 49 ms 82496 KB Output is correct
12 Correct 42 ms 70732 KB Output is correct
13 Correct 47 ms 82500 KB Output is correct
14 Correct 48 ms 82420 KB Output is correct
15 Correct 50 ms 82528 KB Output is correct
16 Correct 50 ms 82528 KB Output is correct
17 Correct 48 ms 82500 KB Output is correct
18 Correct 49 ms 82500 KB Output is correct
19 Correct 52 ms 82468 KB Output is correct
20 Correct 51 ms 82436 KB Output is correct
21 Correct 51 ms 82500 KB Output is correct
22 Correct 50 ms 82416 KB Output is correct
23 Correct 53 ms 82496 KB Output is correct
24 Correct 51 ms 82460 KB Output is correct
25 Correct 51 ms 82532 KB Output is correct
26 Correct 48 ms 82552 KB Output is correct
27 Correct 52 ms 82508 KB Output is correct
28 Correct 49 ms 82500 KB Output is correct
29 Correct 50 ms 82552 KB Output is correct
30 Correct 52 ms 82500 KB Output is correct
31 Correct 60 ms 82424 KB Output is correct
32 Correct 52 ms 82436 KB Output is correct
33 Correct 51 ms 82520 KB Output is correct
34 Correct 49 ms 82508 KB Output is correct
35 Correct 51 ms 82508 KB Output is correct
36 Correct 49 ms 82460 KB Output is correct
37 Correct 51 ms 82500 KB Output is correct
38 Correct 50 ms 82436 KB Output is correct
39 Correct 52 ms 82484 KB Output is correct
40 Correct 50 ms 82528 KB Output is correct
41 Correct 51 ms 82420 KB Output is correct
42 Correct 51 ms 82536 KB Output is correct
43 Correct 51 ms 82528 KB Output is correct
44 Correct 50 ms 82444 KB Output is correct
45 Correct 48 ms 82412 KB Output is correct
46 Correct 54 ms 82492 KB Output is correct
47 Correct 52 ms 82500 KB Output is correct
48 Correct 49 ms 82452 KB Output is correct
49 Correct 50 ms 82500 KB Output is correct
50 Correct 50 ms 82500 KB Output is correct
51 Correct 51 ms 82524 KB Output is correct
52 Correct 51 ms 82520 KB Output is correct
53 Correct 51 ms 82468 KB Output is correct
54 Correct 57 ms 82536 KB Output is correct
55 Correct 55 ms 82500 KB Output is correct
56 Correct 49 ms 82444 KB Output is correct
57 Correct 53 ms 82520 KB Output is correct
58 Correct 51 ms 82464 KB Output is correct
59 Correct 49 ms 82440 KB Output is correct
60 Correct 51 ms 82764 KB Output is correct
61 Correct 51 ms 82748 KB Output is correct
62 Correct 52 ms 82764 KB Output is correct
63 Correct 59 ms 83092 KB Output is correct
64 Correct 57 ms 83392 KB Output is correct
65 Correct 56 ms 82944 KB Output is correct
66 Correct 55 ms 83020 KB Output is correct
67 Correct 55 ms 83448 KB Output is correct
68 Correct 53 ms 82800 KB Output is correct
69 Correct 51 ms 82628 KB Output is correct
70 Correct 51 ms 71304 KB Output is correct
71 Correct 53 ms 82720 KB Output is correct
72 Correct 53 ms 82756 KB Output is correct
73 Correct 62 ms 82884 KB Output is correct
74 Correct 54 ms 83268 KB Output is correct
75 Correct 58 ms 83028 KB Output is correct
76 Correct 58 ms 83080 KB Output is correct
77 Correct 55 ms 82756 KB Output is correct
78 Correct 60 ms 82708 KB Output is correct
79 Correct 53 ms 82700 KB Output is correct
80 Correct 55 ms 83136 KB Output is correct
81 Correct 56 ms 83148 KB Output is correct
82 Correct 59 ms 83012 KB Output is correct
83 Correct 57 ms 83232 KB Output is correct
84 Correct 57 ms 83068 KB Output is correct
85 Correct 55 ms 83216 KB Output is correct
86 Correct 56 ms 83104 KB Output is correct
87 Correct 57 ms 83216 KB Output is correct
88 Correct 57 ms 83140 KB Output is correct
89 Correct 60 ms 82980 KB Output is correct
90 Correct 51 ms 82752 KB Output is correct
91 Correct 55 ms 83140 KB Output is correct
92 Correct 54 ms 83260 KB Output is correct
93 Correct 58 ms 83272 KB Output is correct
94 Correct 60 ms 82904 KB Output is correct
95 Correct 58 ms 83012 KB Output is correct
96 Correct 56 ms 82792 KB Output is correct
97 Correct 52 ms 82944 KB Output is correct
98 Correct 54 ms 82844 KB Output is correct
99 Correct 53 ms 82884 KB Output is correct
100 Correct 56 ms 83216 KB Output is correct
101 Correct 56 ms 82992 KB Output is correct
102 Correct 59 ms 83224 KB Output is correct
103 Correct 53 ms 83140 KB Output is correct
104 Correct 56 ms 83144 KB Output is correct
105 Correct 56 ms 83240 KB Output is correct
106 Correct 56 ms 83080 KB Output is correct
107 Correct 55 ms 83268 KB Output is correct
108 Correct 67 ms 83032 KB Output is correct
109 Correct 60 ms 83016 KB Output is correct
110 Correct 55 ms 83196 KB Output is correct
111 Correct 55 ms 83040 KB Output is correct
112 Correct 55 ms 83196 KB Output is correct
113 Correct 57 ms 83160 KB Output is correct
114 Correct 56 ms 83176 KB Output is correct
115 Correct 56 ms 83012 KB Output is correct
116 Correct 58 ms 83332 KB Output is correct
117 Correct 59 ms 83036 KB Output is correct
118 Correct 56 ms 83244 KB Output is correct
119 Correct 55 ms 83012 KB Output is correct
120 Correct 57 ms 83232 KB Output is correct
121 Correct 63 ms 83196 KB Output is correct
122 Correct 60 ms 83224 KB Output is correct
123 Correct 58 ms 83156 KB Output is correct
124 Correct 56 ms 83256 KB Output is correct
125 Correct 56 ms 83108 KB Output is correct
126 Correct 56 ms 83004 KB Output is correct
127 Correct 57 ms 83388 KB Output is correct
128 Correct 54 ms 82400 KB Output is correct
129 Correct 345 ms 92840 KB Output is correct
130 Correct 338 ms 100012 KB Output is correct
131 Correct 331 ms 102056 KB Output is correct
132 Correct 312 ms 91684 KB Output is correct
133 Correct 385 ms 96112 KB Output is correct
134 Correct 294 ms 96656 KB Output is correct
135 Correct 418 ms 91404 KB Output is correct
136 Correct 347 ms 94756 KB Output is correct
137 Correct 292 ms 95476 KB Output is correct
138 Correct 315 ms 101928 KB Output is correct
139 Correct 799 ms 109612 KB Output is correct
140 Correct 844 ms 120224 KB Output is correct
141 Correct 854 ms 111656 KB Output is correct
142 Correct 1006 ms 115504 KB Output is correct
143 Correct 991 ms 114572 KB Output is correct
144 Correct 954 ms 111252 KB Output is correct
145 Correct 995 ms 128028 KB Output is correct
146 Correct 643 ms 114908 KB Output is correct
147 Correct 787 ms 126932 KB Output is correct
148 Correct 1053 ms 104504 KB Output is correct
149 Correct 382 ms 93476 KB Output is correct
150 Correct 457 ms 92932 KB Output is correct
151 Correct 432 ms 96040 KB Output is correct
152 Correct 370 ms 92396 KB Output is correct
153 Correct 413 ms 92016 KB Output is correct
154 Correct 368 ms 91436 KB Output is correct
155 Correct 365 ms 95336 KB Output is correct
156 Correct 307 ms 96480 KB Output is correct
157 Correct 320 ms 93968 KB Output is correct
158 Correct 326 ms 95164 KB Output is correct
159 Correct 328 ms 99960 KB Output is correct
160 Correct 751 ms 108356 KB Output is correct
161 Correct 862 ms 120268 KB Output is correct
162 Correct 980 ms 126108 KB Output is correct
163 Correct 998 ms 119472 KB Output is correct
164 Correct 979 ms 124828 KB Output is correct
165 Correct 1028 ms 112944 KB Output is correct
166 Correct 872 ms 114140 KB Output is correct
167 Correct 997 ms 121420 KB Output is correct
168 Correct 764 ms 116920 KB Output is correct
169 Correct 663 ms 117624 KB Output is correct
170 Correct 571 ms 113284 KB Output is correct
171 Correct 1002 ms 104836 KB Output is correct
172 Correct 1038 ms 106788 KB Output is correct
173 Correct 886 ms 114944 KB Output is correct
174 Correct 922 ms 115888 KB Output is correct
175 Correct 905 ms 112068 KB Output is correct
176 Correct 905 ms 111624 KB Output is correct
177 Correct 841 ms 111752 KB Output is correct
178 Correct 963 ms 125652 KB Output is correct
179 Correct 697 ms 117612 KB Output is correct
180 Correct 663 ms 117536 KB Output is correct
181 Correct 701 ms 104092 KB Output is correct
182 Correct 940 ms 117212 KB Output is correct
183 Correct 905 ms 117960 KB Output is correct
184 Correct 809 ms 111428 KB Output is correct
185 Correct 870 ms 109172 KB Output is correct
186 Correct 764 ms 106708 KB Output is correct
187 Correct 3204 ms 172980 KB Output is correct
188 Correct 2619 ms 169772 KB Output is correct
189 Correct 3058 ms 186552 KB Output is correct
190 Correct 2607 ms 169404 KB Output is correct
191 Correct 2683 ms 169784 KB Output is correct
192 Correct 2493 ms 169556 KB Output is correct
193 Correct 2867 ms 178620 KB Output is correct
194 Correct 2832 ms 179092 KB Output is correct
195 Correct 2813 ms 163564 KB Output is correct
196 Correct 2528 ms 153064 KB Output is correct
197 Correct 2564 ms 151368 KB Output is correct
198 Correct 2697 ms 156704 KB Output is correct
199 Correct 3224 ms 149656 KB Output is correct
200 Correct 2782 ms 155444 KB Output is correct
201 Correct 2820 ms 150132 KB Output is correct
202 Correct 3790 ms 151952 KB Output is correct
203 Correct 2793 ms 164720 KB Output is correct
204 Correct 3612 ms 152008 KB Output is correct
205 Correct 3624 ms 151964 KB Output is correct
206 Correct 3447 ms 151984 KB Output is correct
207 Correct 3506 ms 151952 KB Output is correct
208 Correct 2884 ms 150176 KB Output is correct
209 Correct 3305 ms 174972 KB Output is correct
210 Correct 2614 ms 161712 KB Output is correct
211 Correct 2893 ms 169408 KB Output is correct
212 Correct 2810 ms 154588 KB Output is correct
213 Correct 2876 ms 163064 KB Output is correct
214 Correct 2881 ms 238864 KB Output is correct
215 Correct 3134 ms 232876 KB Output is correct
216 Correct 3116 ms 230540 KB Output is correct
217 Correct 3312 ms 150624 KB Output is correct
218 Correct 3199 ms 149396 KB Output is correct
219 Correct 2823 ms 179052 KB Output is correct
220 Correct 2734 ms 187336 KB Output is correct
221 Correct 2653 ms 156820 KB Output is correct
222 Correct 2625 ms 159800 KB Output is correct
223 Correct 3150 ms 201112 KB Output is correct
224 Correct 3471 ms 175244 KB Output is correct
225 Correct 2780 ms 179416 KB Output is correct
226 Correct 3062 ms 256344 KB Output is correct
227 Correct 3180 ms 149080 KB Output is correct
228 Correct 3320 ms 148924 KB Output is correct
229 Correct 2931 ms 173592 KB Output is correct
230 Correct 2574 ms 165112 KB Output is correct
231 Correct 2534 ms 157264 KB Output is correct
232 Correct 2561 ms 180964 KB Output is correct
233 Correct 2965 ms 210312 KB Output is correct
234 Correct 2607 ms 162636 KB Output is correct
235 Correct 2983 ms 190860 KB Output is correct
236 Correct 2573 ms 153268 KB Output is correct
237 Correct 2675 ms 153700 KB Output is correct
238 Correct 2626 ms 165024 KB Output is correct
239 Correct 2472 ms 155388 KB Output is correct
240 Correct 2718 ms 161288 KB Output is correct
241 Correct 2826 ms 186564 KB Output is correct
242 Correct 2844 ms 172192 KB Output is correct