oj.uz

Submission #473975

# Submission time Handle Problem Language Result Execution time Memory
473975 2021-09-16T13:43:34 Z model_code Wells (CEOI21_wells) C++17
60 / 100
 3304 ms 256420 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+1);
 
  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
18.0 / 30.0

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

Subtask #2
12.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 50 ms 82436 KB Output is partially correct
2 Partially correct 50 ms 82500 KB Output is partially correct
3 Partially correct 49 ms 82436 KB Output is partially correct
4 Partially correct 52 ms 82544 KB Output is partially correct
5 Partially correct 48 ms 82516 KB Output is partially correct
6 Partially correct 48 ms 82472 KB Output is partially correct
7 Partially correct 47 ms 82424 KB Output is partially correct
8 Partially correct 48 ms 82452 KB Output is partially correct
9 Partially correct 48 ms 82508 KB Output is partially correct
10 Partially correct 49 ms 82500 KB Output is partially correct
11 Partially correct 48 ms 82472 KB Output is partially correct
12 Correct 44 ms 70784 KB Output is correct
13 Partially correct 50 ms 82428 KB Output is partially correct
14 Partially correct 49 ms 82552 KB Output is partially correct
15 Partially correct 48 ms 82500 KB Output is partially correct
16 Partially correct 47 ms 82500 KB Output is partially correct
17 Partially correct 48 ms 82492 KB Output is partially correct
18 Partially correct 48 ms 82420 KB Output is partially correct
19 Partially correct 48 ms 82480 KB Output is partially correct
20 Partially correct 48 ms 82480 KB Output is partially correct
21 Partially correct 48 ms 82496 KB Output is partially correct
22 Partially correct 50 ms 82548 KB Output is partially correct
23 Partially correct 48 ms 82500 KB Output is partially correct
24 Partially correct 48 ms 82500 KB Output is partially correct
25 Partially correct 48 ms 82512 KB Output is partially correct
26 Partially correct 48 ms 82492 KB Output is partially correct
27 Partially correct 48 ms 82500 KB Output is partially correct
28 Partially correct 46 ms 82524 KB Output is partially correct
29 Partially correct 55 ms 82468 KB Output is partially correct
30 Partially correct 48 ms 82416 KB Output is partially correct
31 Partially correct 50 ms 82428 KB Output is partially correct
32 Partially correct 49 ms 82536 KB Output is partially correct
33 Partially correct 47 ms 82496 KB Output is partially correct
34 Partially correct 52 ms 82496 KB Output is partially correct
35 Partially correct 49 ms 82524 KB Output is partially correct
36 Partially correct 48 ms 82484 KB Output is partially correct
37 Partially correct 49 ms 82448 KB Output is partially correct
38 Partially correct 48 ms 82536 KB Output is partially correct
39 Partially correct 48 ms 82524 KB Output is partially correct
40 Partially correct 49 ms 82524 KB Output is partially correct
41 Partially correct 54 ms 82536 KB Output is partially correct
42 Partially correct 48 ms 82528 KB Output is partially correct
43 Partially correct 50 ms 82500 KB Output is partially correct
44 Partially correct 47 ms 82500 KB Output is partially correct
45 Partially correct 48 ms 82484 KB Output is partially correct
46 Partially correct 50 ms 82472 KB Output is partially correct
47 Partially correct 48 ms 82448 KB Output is partially correct
48 Partially correct 47 ms 82552 KB Output is partially correct
49 Partially correct 47 ms 82516 KB Output is partially correct
50 Partially correct 52 ms 82496 KB Output is partially correct
51 Partially correct 48 ms 82500 KB Output is partially correct
52 Partially correct 48 ms 82556 KB Output is partially correct
53 Partially correct 47 ms 82464 KB Output is partially correct
54 Partially correct 49 ms 82492 KB Output is partially correct
55 Partially correct 58 ms 82492 KB Output is partially correct
56 Partially correct 53 ms 82612 KB Output is partially correct
57 Partially correct 48 ms 82536 KB Output is partially correct
58 Partially correct 48 ms 82512 KB Output is partially correct
59 Partially correct 50 ms 82436 KB Output is partially correct
60 Partially correct 48 ms 82764 KB Output is partially correct
61 Partially correct 48 ms 82592 KB Output is partially correct
62 Partially correct 67 ms 82740 KB Output is partially correct
63 Partially correct 55 ms 83084 KB Output is partially correct
64 Partially correct 53 ms 83500 KB Output is partially correct
65 Partially correct 53 ms 82912 KB Output is partially correct
66 Partially correct 54 ms 82952 KB Output is partially correct
67 Partially correct 56 ms 83440 KB Output is partially correct
68 Partially correct 50 ms 82680 KB Output is partially correct
69 Partially correct 49 ms 82712 KB Output is partially correct
70 Correct 47 ms 71316 KB Output is correct
71 Partially correct 50 ms 82708 KB Output is partially correct
72 Partially correct 50 ms 82752 KB Output is partially correct
73 Partially correct 52 ms 82796 KB Output is partially correct
74 Partially correct 59 ms 83372 KB Output is partially correct
75 Partially correct 54 ms 83068 KB Output is partially correct
76 Partially correct 53 ms 83012 KB Output is partially correct
77 Partially correct 51 ms 82644 KB Output is partially correct
78 Partially correct 58 ms 82804 KB Output is partially correct
79 Partially correct 52 ms 82744 KB Output is partially correct
80 Partially correct 51 ms 83124 KB Output is partially correct
81 Partially correct 53 ms 83140 KB Output is partially correct
82 Partially correct 55 ms 83008 KB Output is partially correct
83 Partially correct 52 ms 83176 KB Output is partially correct
84 Partially correct 53 ms 83088 KB Output is partially correct
85 Partially correct 54 ms 83264 KB Output is partially correct
86 Partially correct 63 ms 83004 KB Output is partially correct
87 Partially correct 55 ms 83140 KB Output is partially correct
88 Partially correct 53 ms 83340 KB Output is partially correct
89 Partially correct 55 ms 83064 KB Output is partially correct
90 Partially correct 49 ms 82828 KB Output is partially correct
91 Partially correct 54 ms 83128 KB Output is partially correct
92 Partially correct 53 ms 83288 KB Output is partially correct
93 Partially correct 53 ms 83140 KB Output is partially correct
94 Partially correct 54 ms 82912 KB Output is partially correct
95 Partially correct 53 ms 82936 KB Output is partially correct
96 Partially correct 50 ms 82816 KB Output is partially correct
97 Partially correct 50 ms 82900 KB Output is partially correct
98 Partially correct 52 ms 82904 KB Output is partially correct
99 Partially correct 53 ms 82852 KB Output is partially correct
100 Partially correct 53 ms 83160 KB Output is partially correct
101 Partially correct 51 ms 83088 KB Output is partially correct
102 Partially correct 55 ms 83168 KB Output is partially correct
103 Partially correct 54 ms 83176 KB Output is partially correct
104 Partially correct 54 ms 83208 KB Output is partially correct
105 Partially correct 55 ms 83180 KB Output is partially correct
106 Partially correct 53 ms 82904 KB Output is partially correct
107 Partially correct 54 ms 83416 KB Output is partially correct
108 Partially correct 54 ms 83012 KB Output is partially correct
109 Partially correct 57 ms 83084 KB Output is partially correct
110 Partially correct 53 ms 83196 KB Output is partially correct
111 Partially correct 54 ms 83148 KB Output is partially correct
112 Partially correct 54 ms 83260 KB Output is partially correct
113 Partially correct 54 ms 83028 KB Output is partially correct
114 Partially correct 53 ms 83168 KB Output is partially correct
115 Partially correct 54 ms 83060 KB Output is partially correct
116 Partially correct 54 ms 83280 KB Output is partially correct
117 Partially correct 54 ms 83036 KB Output is partially correct
118 Partially correct 58 ms 83308 KB Output is partially correct
119 Partially correct 54 ms 83132 KB Output is partially correct
120 Partially correct 55 ms 83268 KB Output is partially correct
121 Partially correct 56 ms 83192 KB Output is partially correct
122 Partially correct 55 ms 83232 KB Output is partially correct
123 Partially correct 55 ms 83164 KB Output is partially correct
124 Partially correct 54 ms 83264 KB Output is partially correct
125 Partially correct 55 ms 83076 KB Output is partially correct
126 Partially correct 55 ms 83012 KB Output is partially correct
127 Partially correct 54 ms 83324 KB Output is partially correct

Subtask #3
12.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 50 ms 82436 KB Output is partially correct
2 Partially correct 50 ms 82500 KB Output is partially correct
3 Partially correct 49 ms 82436 KB Output is partially correct
4 Partially correct 52 ms 82544 KB Output is partially correct
5 Partially correct 48 ms 82516 KB Output is partially correct
6 Partially correct 48 ms 82472 KB Output is partially correct
7 Partially correct 47 ms 82424 KB Output is partially correct
8 Partially correct 48 ms 82452 KB Output is partially correct
9 Partially correct 48 ms 82508 KB Output is partially correct
10 Partially correct 49 ms 82500 KB Output is partially correct
11 Partially correct 48 ms 82472 KB Output is partially correct
12 Correct 44 ms 70784 KB Output is correct
13 Partially correct 50 ms 82428 KB Output is partially correct
14 Partially correct 49 ms 82552 KB Output is partially correct
15 Partially correct 48 ms 82500 KB Output is partially correct
16 Partially correct 47 ms 82500 KB Output is partially correct
17 Partially correct 48 ms 82492 KB Output is partially correct
18 Partially correct 48 ms 82420 KB Output is partially correct
19 Partially correct 48 ms 82480 KB Output is partially correct
20 Partially correct 48 ms 82480 KB Output is partially correct
21 Partially correct 48 ms 82496 KB Output is partially correct
22 Partially correct 50 ms 82548 KB Output is partially correct
23 Partially correct 48 ms 82500 KB Output is partially correct
24 Partially correct 48 ms 82500 KB Output is partially correct
25 Partially correct 48 ms 82512 KB Output is partially correct
26 Partially correct 48 ms 82492 KB Output is partially correct
27 Partially correct 48 ms 82500 KB Output is partially correct
28 Partially correct 46 ms 82524 KB Output is partially correct
29 Partially correct 55 ms 82468 KB Output is partially correct
30 Partially correct 48 ms 82416 KB Output is partially correct
31 Partially correct 50 ms 82428 KB Output is partially correct
32 Partially correct 49 ms 82536 KB Output is partially correct
33 Partially correct 47 ms 82496 KB Output is partially correct
34 Partially correct 52 ms 82496 KB Output is partially correct
35 Partially correct 49 ms 82524 KB Output is partially correct
36 Partially correct 48 ms 82484 KB Output is partially correct
37 Partially correct 49 ms 82448 KB Output is partially correct
38 Partially correct 48 ms 82536 KB Output is partially correct
39 Partially correct 48 ms 82524 KB Output is partially correct
40 Partially correct 49 ms 82524 KB Output is partially correct
41 Partially correct 54 ms 82536 KB Output is partially correct
42 Partially correct 48 ms 82528 KB Output is partially correct
43 Partially correct 50 ms 82500 KB Output is partially correct
44 Partially correct 47 ms 82500 KB Output is partially correct
45 Partially correct 48 ms 82484 KB Output is partially correct
46 Partially correct 50 ms 82472 KB Output is partially correct
47 Partially correct 48 ms 82448 KB Output is partially correct
48 Partially correct 47 ms 82552 KB Output is partially correct
49 Partially correct 47 ms 82516 KB Output is partially correct
50 Partially correct 52 ms 82496 KB Output is partially correct
51 Partially correct 48 ms 82500 KB Output is partially correct
52 Partially correct 48 ms 82556 KB Output is partially correct
53 Partially correct 47 ms 82464 KB Output is partially correct
54 Partially correct 49 ms 82492 KB Output is partially correct
55 Partially correct 58 ms 82492 KB Output is partially correct
56 Partially correct 53 ms 82612 KB Output is partially correct
57 Partially correct 48 ms 82536 KB Output is partially correct
58 Partially correct 48 ms 82512 KB Output is partially correct
59 Partially correct 50 ms 82436 KB Output is partially correct
60 Partially correct 48 ms 82764 KB Output is partially correct
61 Partially correct 48 ms 82592 KB Output is partially correct
62 Partially correct 67 ms 82740 KB Output is partially correct
63 Partially correct 55 ms 83084 KB Output is partially correct
64 Partially correct 53 ms 83500 KB Output is partially correct
65 Partially correct 53 ms 82912 KB Output is partially correct
66 Partially correct 54 ms 82952 KB Output is partially correct
67 Partially correct 56 ms 83440 KB Output is partially correct
68 Partially correct 50 ms 82680 KB Output is partially correct
69 Partially correct 49 ms 82712 KB Output is partially correct
70 Correct 47 ms 71316 KB Output is correct
71 Partially correct 50 ms 82708 KB Output is partially correct
72 Partially correct 50 ms 82752 KB Output is partially correct
73 Partially correct 52 ms 82796 KB Output is partially correct
74 Partially correct 59 ms 83372 KB Output is partially correct
75 Partially correct 54 ms 83068 KB Output is partially correct
76 Partially correct 53 ms 83012 KB Output is partially correct
77 Partially correct 51 ms 82644 KB Output is partially correct
78 Partially correct 58 ms 82804 KB Output is partially correct
79 Partially correct 52 ms 82744 KB Output is partially correct
80 Partially correct 51 ms 83124 KB Output is partially correct
81 Partially correct 53 ms 83140 KB Output is partially correct
82 Partially correct 55 ms 83008 KB Output is partially correct
83 Partially correct 52 ms 83176 KB Output is partially correct
84 Partially correct 53 ms 83088 KB Output is partially correct
85 Partially correct 54 ms 83264 KB Output is partially correct
86 Partially correct 63 ms 83004 KB Output is partially correct
87 Partially correct 55 ms 83140 KB Output is partially correct
88 Partially correct 53 ms 83340 KB Output is partially correct
89 Partially correct 55 ms 83064 KB Output is partially correct
90 Partially correct 49 ms 82828 KB Output is partially correct
91 Partially correct 54 ms 83128 KB Output is partially correct
92 Partially correct 53 ms 83288 KB Output is partially correct
93 Partially correct 53 ms 83140 KB Output is partially correct
94 Partially correct 54 ms 82912 KB Output is partially correct
95 Partially correct 53 ms 82936 KB Output is partially correct
96 Partially correct 50 ms 82816 KB Output is partially correct
97 Partially correct 50 ms 82900 KB Output is partially correct
98 Partially correct 52 ms 82904 KB Output is partially correct
99 Partially correct 53 ms 82852 KB Output is partially correct
100 Partially correct 53 ms 83160 KB Output is partially correct
101 Partially correct 51 ms 83088 KB Output is partially correct
102 Partially correct 55 ms 83168 KB Output is partially correct
103 Partially correct 54 ms 83176 KB Output is partially correct
104 Partially correct 54 ms 83208 KB Output is partially correct
105 Partially correct 55 ms 83180 KB Output is partially correct
106 Partially correct 53 ms 82904 KB Output is partially correct
107 Partially correct 54 ms 83416 KB Output is partially correct
108 Partially correct 54 ms 83012 KB Output is partially correct
109 Partially correct 57 ms 83084 KB Output is partially correct
110 Partially correct 53 ms 83196 KB Output is partially correct
111 Partially correct 54 ms 83148 KB Output is partially correct
112 Partially correct 54 ms 83260 KB Output is partially correct
113 Partially correct 54 ms 83028 KB Output is partially correct
114 Partially correct 53 ms 83168 KB Output is partially correct
115 Partially correct 54 ms 83060 KB Output is partially correct
116 Partially correct 54 ms 83280 KB Output is partially correct
117 Partially correct 54 ms 83036 KB Output is partially correct
118 Partially correct 58 ms 83308 KB Output is partially correct
119 Partially correct 54 ms 83132 KB Output is partially correct
120 Partially correct 55 ms 83268 KB Output is partially correct
121 Partially correct 56 ms 83192 KB Output is partially correct
122 Partially correct 55 ms 83232 KB Output is partially correct
123 Partially correct 55 ms 83164 KB Output is partially correct
124 Partially correct 54 ms 83264 KB Output is partially correct
125 Partially correct 55 ms 83076 KB Output is partially correct
126 Partially correct 55 ms 83012 KB Output is partially correct
127 Partially correct 54 ms 83324 KB Output is partially correct
128 Partially correct 49 ms 82420 KB Output is partially correct
129 Partially correct 329 ms 92900 KB Output is partially correct
130 Partially correct 338 ms 100104 KB Output is partially correct
131 Partially correct 346 ms 102124 KB Output is partially correct
132 Partially correct 349 ms 91584 KB Output is partially correct
133 Partially correct 335 ms 96044 KB Output is partially correct
134 Partially correct 329 ms 96724 KB Output is partially correct
135 Partially correct 359 ms 91536 KB Output is partially correct
136 Partially correct 367 ms 94716 KB Output is partially correct
137 Partially correct 268 ms 95520 KB Output is partially correct
138 Partially correct 309 ms 101916 KB Output is partially correct
139 Correct 789 ms 109772 KB Output is correct
140 Partially correct 826 ms 120328 KB Output is partially correct
141 Partially correct 852 ms 111728 KB Output is partially correct
142 Partially correct 985 ms 115504 KB Output is partially correct
143 Partially correct 942 ms 114564 KB Output is partially correct
144 Partially correct 1000 ms 111396 KB Output is partially correct
145 Partially correct 922 ms 128080 KB Output is partially correct
146 Partially correct 645 ms 114884 KB Output is partially correct
147 Partially correct 793 ms 126892 KB Output is partially correct
148 Partially correct 1004 ms 104624 KB Output is partially correct
149 Partially correct 374 ms 93452 KB Output is partially correct
150 Partially correct 421 ms 93036 KB Output is partially correct
151 Partially correct 345 ms 96212 KB Output is partially correct
152 Partially correct 347 ms 92288 KB Output is partially correct
153 Partially correct 379 ms 92164 KB Output is partially correct
154 Partially correct 409 ms 91528 KB Output is partially correct
155 Partially correct 381 ms 95392 KB Output is partially correct
156 Partially correct 350 ms 96436 KB Output is partially correct
157 Partially correct 304 ms 94000 KB Output is partially correct
158 Partially correct 295 ms 95128 KB Output is partially correct
159 Partially correct 276 ms 99892 KB Output is partially correct
160 Partially correct 656 ms 108320 KB Output is partially correct
161 Partially correct 806 ms 120296 KB Output is partially correct
162 Partially correct 974 ms 126140 KB Output is partially correct
163 Partially correct 926 ms 119516 KB Output is partially correct
164 Partially correct 926 ms 124780 KB Output is partially correct
165 Partially correct 972 ms 112980 KB Output is partially correct
166 Partially correct 846 ms 114112 KB Output is partially correct
167 Partially correct 945 ms 121488 KB Output is partially correct
168 Partially correct 699 ms 117020 KB Output is partially correct
169 Partially correct 615 ms 117544 KB Output is partially correct
170 Partially correct 530 ms 113292 KB Output is partially correct
171 Partially correct 995 ms 104916 KB Output is partially correct
172 Partially correct 1010 ms 106568 KB Output is partially correct
173 Partially correct 804 ms 114944 KB Output is partially correct
174 Partially correct 868 ms 115932 KB Output is partially correct
175 Partially correct 812 ms 112216 KB Output is partially correct
176 Partially correct 801 ms 111588 KB Output is partially correct
177 Partially correct 817 ms 111780 KB Output is partially correct
178 Partially correct 918 ms 125752 KB Output is partially correct
179 Partially correct 607 ms 117628 KB Output is partially correct
180 Partially correct 641 ms 117548 KB Output is partially correct
181 Partially correct 640 ms 104136 KB Output is partially correct
182 Partially correct 863 ms 117232 KB Output is partially correct
183 Partially correct 840 ms 117960 KB Output is partially correct
184 Partially correct 765 ms 111440 KB Output is partially correct
185 Partially correct 802 ms 109208 KB Output is partially correct
186 Partially correct 668 ms 106860 KB Output is partially correct

Subtask #4
18.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 50 ms 82436 KB Output is partially correct
2 Partially correct 50 ms 82500 KB Output is partially correct
3 Partially correct 49 ms 82436 KB Output is partially correct
4 Partially correct 52 ms 82544 KB Output is partially correct
5 Partially correct 48 ms 82516 KB Output is partially correct
6 Partially correct 48 ms 82472 KB Output is partially correct
7 Partially correct 47 ms 82424 KB Output is partially correct
8 Partially correct 48 ms 82452 KB Output is partially correct
9 Partially correct 48 ms 82508 KB Output is partially correct
10 Partially correct 49 ms 82500 KB Output is partially correct
11 Partially correct 48 ms 82472 KB Output is partially correct
12 Correct 44 ms 70784 KB Output is correct
13 Partially correct 50 ms 82428 KB Output is partially correct
14 Partially correct 49 ms 82552 KB Output is partially correct
15 Partially correct 48 ms 82500 KB Output is partially correct
16 Partially correct 47 ms 82500 KB Output is partially correct
17 Partially correct 48 ms 82492 KB Output is partially correct
18 Partially correct 48 ms 82420 KB Output is partially correct
19 Partially correct 48 ms 82480 KB Output is partially correct
20 Partially correct 48 ms 82480 KB Output is partially correct
21 Partially correct 48 ms 82496 KB Output is partially correct
22 Partially correct 50 ms 82548 KB Output is partially correct
23 Partially correct 48 ms 82500 KB Output is partially correct
24 Partially correct 48 ms 82500 KB Output is partially correct
25 Partially correct 48 ms 82512 KB Output is partially correct
26 Partially correct 48 ms 82492 KB Output is partially correct
27 Partially correct 48 ms 82500 KB Output is partially correct
28 Partially correct 46 ms 82524 KB Output is partially correct
29 Partially correct 55 ms 82468 KB Output is partially correct
30 Partially correct 48 ms 82416 KB Output is partially correct
31 Partially correct 50 ms 82428 KB Output is partially correct
32 Partially correct 49 ms 82536 KB Output is partially correct
33 Partially correct 47 ms 82496 KB Output is partially correct
34 Partially correct 52 ms 82496 KB Output is partially correct
35 Partially correct 49 ms 82524 KB Output is partially correct
36 Partially correct 48 ms 82484 KB Output is partially correct
37 Partially correct 49 ms 82448 KB Output is partially correct
38 Partially correct 48 ms 82536 KB Output is partially correct
39 Partially correct 48 ms 82524 KB Output is partially correct
40 Partially correct 49 ms 82524 KB Output is partially correct
41 Partially correct 54 ms 82536 KB Output is partially correct
42 Partially correct 48 ms 82528 KB Output is partially correct
43 Partially correct 50 ms 82500 KB Output is partially correct
44 Partially correct 47 ms 82500 KB Output is partially correct
45 Partially correct 48 ms 82484 KB Output is partially correct
46 Partially correct 50 ms 82472 KB Output is partially correct
47 Partially correct 48 ms 82448 KB Output is partially correct
48 Partially correct 47 ms 82552 KB Output is partially correct
49 Partially correct 47 ms 82516 KB Output is partially correct
50 Partially correct 52 ms 82496 KB Output is partially correct
51 Partially correct 48 ms 82500 KB Output is partially correct
52 Partially correct 48 ms 82556 KB Output is partially correct
53 Partially correct 47 ms 82464 KB Output is partially correct
54 Partially correct 49 ms 82492 KB Output is partially correct
55 Partially correct 58 ms 82492 KB Output is partially correct
56 Partially correct 53 ms 82612 KB Output is partially correct
57 Partially correct 48 ms 82536 KB Output is partially correct
58 Partially correct 48 ms 82512 KB Output is partially correct
59 Partially correct 50 ms 82436 KB Output is partially correct
60 Partially correct 48 ms 82764 KB Output is partially correct
61 Partially correct 48 ms 82592 KB Output is partially correct
62 Partially correct 67 ms 82740 KB Output is partially correct
63 Partially correct 55 ms 83084 KB Output is partially correct
64 Partially correct 53 ms 83500 KB Output is partially correct
65 Partially correct 53 ms 82912 KB Output is partially correct
66 Partially correct 54 ms 82952 KB Output is partially correct
67 Partially correct 56 ms 83440 KB Output is partially correct
68 Partially correct 50 ms 82680 KB Output is partially correct
69 Partially correct 49 ms 82712 KB Output is partially correct
70 Correct 47 ms 71316 KB Output is correct
71 Partially correct 50 ms 82708 KB Output is partially correct
72 Partially correct 50 ms 82752 KB Output is partially correct
73 Partially correct 52 ms 82796 KB Output is partially correct
74 Partially correct 59 ms 83372 KB Output is partially correct
75 Partially correct 54 ms 83068 KB Output is partially correct
76 Partially correct 53 ms 83012 KB Output is partially correct
77 Partially correct 51 ms 82644 KB Output is partially correct
78 Partially correct 58 ms 82804 KB Output is partially correct
79 Partially correct 52 ms 82744 KB Output is partially correct
80 Partially correct 51 ms 83124 KB Output is partially correct
81 Partially correct 53 ms 83140 KB Output is partially correct
82 Partially correct 55 ms 83008 KB Output is partially correct
83 Partially correct 52 ms 83176 KB Output is partially correct
84 Partially correct 53 ms 83088 KB Output is partially correct
85 Partially correct 54 ms 83264 KB Output is partially correct
86 Partially correct 63 ms 83004 KB Output is partially correct
87 Partially correct 55 ms 83140 KB Output is partially correct
88 Partially correct 53 ms 83340 KB Output is partially correct
89 Partially correct 55 ms 83064 KB Output is partially correct
90 Partially correct 49 ms 82828 KB Output is partially correct
91 Partially correct 54 ms 83128 KB Output is partially correct
92 Partially correct 53 ms 83288 KB Output is partially correct
93 Partially correct 53 ms 83140 KB Output is partially correct
94 Partially correct 54 ms 82912 KB Output is partially correct
95 Partially correct 53 ms 82936 KB Output is partially correct
96 Partially correct 50 ms 82816 KB Output is partially correct
97 Partially correct 50 ms 82900 KB Output is partially correct
98 Partially correct 52 ms 82904 KB Output is partially correct
99 Partially correct 53 ms 82852 KB Output is partially correct
100 Partially correct 53 ms 83160 KB Output is partially correct
101 Partially correct 51 ms 83088 KB Output is partially correct
102 Partially correct 55 ms 83168 KB Output is partially correct
103 Partially correct 54 ms 83176 KB Output is partially correct
104 Partially correct 54 ms 83208 KB Output is partially correct
105 Partially correct 55 ms 83180 KB Output is partially correct
106 Partially correct 53 ms 82904 KB Output is partially correct
107 Partially correct 54 ms 83416 KB Output is partially correct
108 Partially correct 54 ms 83012 KB Output is partially correct
109 Partially correct 57 ms 83084 KB Output is partially correct
110 Partially correct 53 ms 83196 KB Output is partially correct
111 Partially correct 54 ms 83148 KB Output is partially correct
112 Partially correct 54 ms 83260 KB Output is partially correct
113 Partially correct 54 ms 83028 KB Output is partially correct
114 Partially correct 53 ms 83168 KB Output is partially correct
115 Partially correct 54 ms 83060 KB Output is partially correct
116 Partially correct 54 ms 83280 KB Output is partially correct
117 Partially correct 54 ms 83036 KB Output is partially correct
118 Partially correct 58 ms 83308 KB Output is partially correct
119 Partially correct 54 ms 83132 KB Output is partially correct
120 Partially correct 55 ms 83268 KB Output is partially correct
121 Partially correct 56 ms 83192 KB Output is partially correct
122 Partially correct 55 ms 83232 KB Output is partially correct
123 Partially correct 55 ms 83164 KB Output is partially correct
124 Partially correct 54 ms 83264 KB Output is partially correct
125 Partially correct 55 ms 83076 KB Output is partially correct
126 Partially correct 55 ms 83012 KB Output is partially correct
127 Partially correct 54 ms 83324 KB Output is partially correct
128 Partially correct 49 ms 82420 KB Output is partially correct
129 Partially correct 329 ms 92900 KB Output is partially correct
130 Partially correct 338 ms 100104 KB Output is partially correct
131 Partially correct 346 ms 102124 KB Output is partially correct
132 Partially correct 349 ms 91584 KB Output is partially correct
133 Partially correct 335 ms 96044 KB Output is partially correct
134 Partially correct 329 ms 96724 KB Output is partially correct
135 Partially correct 359 ms 91536 KB Output is partially correct
136 Partially correct 367 ms 94716 KB Output is partially correct
137 Partially correct 268 ms 95520 KB Output is partially correct
138 Partially correct 309 ms 101916 KB Output is partially correct
139 Correct 789 ms 109772 KB Output is correct
140 Partially correct 826 ms 120328 KB Output is partially correct
141 Partially correct 852 ms 111728 KB Output is partially correct
142 Partially correct 985 ms 115504 KB Output is partially correct
143 Partially correct 942 ms 114564 KB Output is partially correct
144 Partially correct 1000 ms 111396 KB Output is partially correct
145 Partially correct 922 ms 128080 KB Output is partially correct
146 Partially correct 645 ms 114884 KB Output is partially correct
147 Partially correct 793 ms 126892 KB Output is partially correct
148 Partially correct 1004 ms 104624 KB Output is partially correct
149 Partially correct 374 ms 93452 KB Output is partially correct
150 Partially correct 421 ms 93036 KB Output is partially correct
151 Partially correct 345 ms 96212 KB Output is partially correct
152 Partially correct 347 ms 92288 KB Output is partially correct
153 Partially correct 379 ms 92164 KB Output is partially correct
154 Partially correct 409 ms 91528 KB Output is partially correct
155 Partially correct 381 ms 95392 KB Output is partially correct
156 Partially correct 350 ms 96436 KB Output is partially correct
157 Partially correct 304 ms 94000 KB Output is partially correct
158 Partially correct 295 ms 95128 KB Output is partially correct
159 Partially correct 276 ms 99892 KB Output is partially correct
160 Partially correct 656 ms 108320 KB Output is partially correct
161 Partially correct 806 ms 120296 KB Output is partially correct
162 Partially correct 974 ms 126140 KB Output is partially correct
163 Partially correct 926 ms 119516 KB Output is partially correct
164 Partially correct 926 ms 124780 KB Output is partially correct
165 Partially correct 972 ms 112980 KB Output is partially correct
166 Partially correct 846 ms 114112 KB Output is partially correct
167 Partially correct 945 ms 121488 KB Output is partially correct
168 Partially correct 699 ms 117020 KB Output is partially correct
169 Partially correct 615 ms 117544 KB Output is partially correct
170 Partially correct 530 ms 113292 KB Output is partially correct
171 Partially correct 995 ms 104916 KB Output is partially correct
172 Partially correct 1010 ms 106568 KB Output is partially correct
173 Partially correct 804 ms 114944 KB Output is partially correct
174 Partially correct 868 ms 115932 KB Output is partially correct
175 Partially correct 812 ms 112216 KB Output is partially correct
176 Partially correct 801 ms 111588 KB Output is partially correct
177 Partially correct 817 ms 111780 KB Output is partially correct
178 Partially correct 918 ms 125752 KB Output is partially correct
179 Partially correct 607 ms 117628 KB Output is partially correct
180 Partially correct 641 ms 117548 KB Output is partially correct
181 Partially correct 640 ms 104136 KB Output is partially correct
182 Partially correct 863 ms 117232 KB Output is partially correct
183 Partially correct 840 ms 117960 KB Output is partially correct
184 Partially correct 765 ms 111440 KB Output is partially correct
185 Partially correct 802 ms 109208 KB Output is partially correct
186 Partially correct 668 ms 106860 KB Output is partially correct
187 Partially correct 2905 ms 173156 KB Output is partially correct
188 Partially correct 2450 ms 169860 KB Output is partially correct
189 Partially correct 2812 ms 186644 KB Output is partially correct
190 Partially correct 2437 ms 169624 KB Output is partially correct
191 Partially correct 2590 ms 169732 KB Output is partially correct
192 Partially correct 2448 ms 169576 KB Output is partially correct
193 Partially correct 2734 ms 178716 KB Output is partially correct
194 Partially correct 2768 ms 179156 KB Output is partially correct
195 Partially correct 2654 ms 163588 KB Output is partially correct
196 Partially correct 2402 ms 153116 KB Output is partially correct
197 Partially correct 2405 ms 151428 KB Output is partially correct
198 Partially correct 2353 ms 156828 KB Output is partially correct
199 Partially correct 2793 ms 149616 KB Output is partially correct
200 Partially correct 2364 ms 155544 KB Output is partially correct
201 Partially correct 2462 ms 150296 KB Output is partially correct
202 Partially correct 3205 ms 152084 KB Output is partially correct
203 Correct 2401 ms 164912 KB Output is correct
204 Partially correct 3167 ms 152020 KB Output is partially correct
205 Partially correct 3126 ms 152068 KB Output is partially correct
206 Partially correct 3250 ms 152020 KB Output is partially correct
207 Partially correct 3122 ms 151992 KB Output is partially correct
208 Partially correct 2771 ms 150204 KB Output is partially correct
209 Partially correct 3145 ms 175116 KB Output is partially correct
210 Partially correct 2435 ms 161912 KB Output is partially correct
211 Partially correct 2771 ms 169528 KB Output is partially correct
212 Partially correct 2618 ms 154640 KB Output is partially correct
213 Partially correct 2719 ms 163076 KB Output is partially correct
214 Partially correct 2742 ms 239028 KB Output is partially correct
215 Partially correct 2823 ms 232780 KB Output is partially correct
216 Partially correct 3128 ms 230468 KB Output is partially correct
217 Partially correct 3227 ms 150688 KB Output is partially correct
218 Partially correct 3132 ms 149492 KB Output is partially correct
219 Partially correct 2794 ms 179156 KB Output is partially correct
220 Partially correct 2686 ms 187356 KB Output is partially correct
221 Partially correct 2614 ms 156904 KB Output is partially correct
222 Partially correct 2574 ms 159792 KB Output is partially correct
223 Partially correct 3050 ms 201064 KB Output is partially correct
224 Partially correct 3304 ms 175288 KB Output is partially correct
225 Partially correct 2681 ms 179228 KB Output is partially correct
226 Partially correct 2956 ms 256420 KB Output is partially correct
227 Partially correct 3122 ms 149040 KB Output is partially correct
228 Partially correct 3236 ms 148964 KB Output is partially correct
229 Partially correct 2807 ms 173616 KB Output is partially correct
230 Partially correct 2497 ms 165100 KB Output is partially correct
231 Partially correct 2531 ms 157260 KB Output is partially correct
232 Partially correct 2535 ms 181108 KB Output is partially correct
233 Partially correct 3020 ms 210232 KB Output is partially correct
234 Partially correct 2621 ms 162640 KB Output is partially correct
235 Partially correct 2899 ms 190860 KB Output is partially correct
236 Partially correct 2587 ms 153324 KB Output is partially correct
237 Partially correct 2534 ms 153620 KB Output is partially correct
238 Partially correct 2560 ms 165000 KB Output is partially correct
239 Partially correct 2445 ms 155568 KB Output is partially correct
240 Partially correct 2637 ms 161368 KB Output is partially correct
241 Partially correct 2750 ms 186732 KB Output is partially correct
242 Partially correct 2792 ms 172124 KB Output is partially correct