답안 #882953

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
882953 2023-12-04T09:00:20 Z MilosMilutinovic Wild Boar (JOI18_wild_boar) C++14
62 / 100
18000 ms 997972 KB
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m, t, l;
  cin >> n >> m >> t >> l;
  vector<vector<pair<int, int>>> g(n);
  for (int i = 0; i < m; i++) {
    int x, y, z;
    cin >> x >> y >> z;
    --x; --y;
    g[x].emplace_back(y, z);
    g[y].emplace_back(x, z);
  }
  vector<int> seq(l);
  for (int i = 0; i < l; i++) {
    cin >> seq[i];
    --seq[i];
  }
  vector<int> deg(n);
  for (int i = 0; i < n; i++) {
    deg[i] = (int) g[i].size();
  }
  vector<vector<int>> idx(n, vector<int>(n));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < deg[i]; j++) {
      idx[i][g[i][j].first] = j;
    }
  }
  const long long inf = (long long) 1e18;
  vector<vector<vector<vector<long long>>>> dist(n, vector<vector<vector<long long>>>(n));
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (i == j) {
        continue;
      }
      dist[i][j].resize(deg[i]);
      for (int k = 0; k < deg[i]; k++) {
        dist[i][j][k] = vector<long long>(deg[j], inf);
      }
    }
  }
  vector<vector<long long>> d(n);
  for (int i = 0; i < n; i++) {
    d[i].resize(deg[i]);
  }
  vector<int> ia(n), ib(n);
  set<tuple<long long, int, int>> que;
  for (int ver = 0; ver < n; ver++) {
    for (int e = 0; e < deg[ver]; e++) {
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < deg[i]; j++) {
          d[i][j] = inf;
        }
        ia[i] = -1;
        ib[i] = -1;
      }
      int to = g[ver][e].first;
      int w = g[ver][e].second;
      d[to][idx[to][ver]] = w;
      que.clear();
      que.emplace(d[to][idx[to][ver]], to, idx[to][ver]);
      ia[to] = idx[to][ver];
      auto Update = [&](int x, int y, long long z) {
        if (ia[x] == y || ib[x] == y) {
          que.erase(que.find({d[x][y], x, y}));
        }
        d[x][y] = z;
        if (ia[x] == y) {
          return;
        }
        if (ib[x] == y) {
          if (d[x][y] < d[x][ia[x]]) {
            swap(ia[x], ib[x]);
          }
          return;
        }
        if (ia[x] == -1) {
          ia[x] = y;
          que.emplace(d[x][y], x, y);
          return;
        }
        if (ib[x] == -1) {
          if (d[x][y] < d[x][ia[x]]) {
            swap(ia[x], ib[x]);
            ia[x] = y;
          } else {
            ib[x] = y;
          }
          que.emplace(d[x][y], x, y);
          return;
        }
        if (d[x][y] >= d[x][ia[x]] && d[x][y] < d[x][ib[x]]) {
          que.erase(que.find({d[x][ib[x]], x, ib[x]}));
          ib[x] = y;
          que.emplace(d[x][y], x, y);
          return;
        }
        if (d[x][y] < d[x][ia[x]]) {
          que.erase(que.find({d[x][ib[x]], x, ib[x]}));
          swap(ia[x], ib[x]);
          ia[x] = y;
          que.emplace(d[x][y], x, y);
        }
      };
      while (!que.empty()) {
        auto it = que.begin();
        int v = get<1>(*it);
        int lst = get<2>(*it);
        que.erase(it);
        for (int i = 0; i < deg[v]; i++) {
          if (i == lst) {
            continue;
          }
          int to = g[v][i].first;
          int w = g[v][i].second;
          if (d[to][idx[to][v]] > d[v][lst] + w) {
            Update(to, idx[to][v], d[v][lst] + w);
            assert((int) que.size() <= 2 * n);
          }
        }
      }
      for (int i = ver + 1; i < n; i++) {
        if (i == ver) {
          continue;
        }
        for (int j = 0; j < deg[i]; j++) {
          dist[ver][i][e][j] = d[i][j];
        }
      }
    }
  }
  vector<vector<vector<vector<int>>>> good(n, vector<vector<vector<int>>>(n, vector<vector<int>>(2)));
  vector<vector<int>> cc(n, vector<int>(2));
  for (int from = 0; from < n; from++) {
    for (int to = 0; to < n; to++) {
      if (from == to) {
        continue;
      }
      vector<pair<int, int>> order;
      for (int i = 0; i < deg[from]; i++) {
        for (int j = 0; j < deg[to]; j++) {
          order.emplace_back(i, j);
        }
      }
      if (from <= to) {
        sort(order.begin(), order.end(), [&](pair<int, int> a, pair<int, int> b) {
          return dist[from][to][a.first][a.second] < dist[from][to][b.first][b.second];
        });
      } else {
        sort(order.begin(), order.end(), [&](pair<int, int> a, pair<int, int> b) {
          return dist[to][from][a.second][a.first] < dist[to][from][b.second][b.first];
        });
      }
      int total = 0;
      for (auto& p : order) {
        if (cc[p.first][0] >= 2 || cc[p.second][1] >= 2) {
          continue;
        }
        good[from][to][0].push_back(p.first);
        good[from][to][1].push_back(p.second);
        cc[p.first][0] += 1;
        cc[p.second][1] += 1;
        total += 1;
        if (total >= 5) {
          break;
        }
      }
      for (int i = 0; i < deg[from]; i++) {
        cc[i][0] = 0;
      }
      for (int i = 0; i < deg[to]; i++) {
        cc[i][1] = 0;
      }
    }
  }
  vector<vector<int>> f(l);
  for (int i = 0; i < l; i++) {
    if (i > 0) {
      for (int j : good[seq[i - 1]][seq[i]][1]) {
        f[i].push_back(j);
      }
    }
    if (i + 1 < l) {
      for (int j : good[seq[i]][seq[i + 1]][0]) {
        f[i].push_back(j);
      }
    }
    sort(f[i].begin(), f[i].end());
    f[i].erase(unique(f[i].begin(), f[i].end()), f[i].end());
  }
  auto Update = [&](int i) {
    f[i].clear();
    if (i > 0) {
      for (int j : good[seq[i - 1]][seq[i]][1]) {
        f[i].push_back(j);
      }
    }
    if (i + 1 < l) {
      for (int j : good[seq[i]][seq[i + 1]][0]) {
        f[i].push_back(j);
      }
    }
    sort(f[i].begin(), f[i].end());
    f[i].erase(unique(f[i].begin(), f[i].end()), f[i].end());
  };
  vector<vector<vector<long long>>> st(4 * l);
  auto Pull = [&](int x) {
    st[x].clear();
    for (int ll = 0; ll < (int) st[x * 2].size(); ll++) {
      for (int lr = 0; lr < (int) st[x * 2][ll].size(); lr++) {
        if (st[x].empty()) {
          st[x].resize((int) st[x * 2].size());
        }
        for (int rl = 0; rl < (int) st[x * 2 + 1].size(); rl++) {
          if (st[x][ll].empty()) {
            st[x][ll] = vector<long long>((int) st[x * 2 + 1][rl].size(), inf);
          }
          assert(st[x * 2 + 1].size() == st[x * 2][ll].size());
          if (lr == rl) {
            continue;
          }
          for (int rr = 0; rr < (int) st[x * 2 + 1][rl].size(); rr++) {
            st[x][ll][rr] = min(st[x][ll][rr], st[x * 2][ll][lr] + st[x * 2 + 1][rl][rr]);
          }
        }
      }
    }
  };
  function<void(int, int, int)> Build = [&](int x, int l, int r) {
    if (l == r) {
      st[x].resize(f[l].size());
      for (int i = 0; i < f[l].size(); i++) {
        st[x][i] = vector<long long>(f[l + 1].size(), inf);
      }
      for (int i = 0; i < f[l].size(); i++) {
        for (int j = 0; j < f[l + 1].size(); j++) {
          if (seq[l] <= seq[l + 1]) {
            st[x][i][j] = min(st[x][i][j], dist[seq[l]][seq[l + 1]][f[l][i]][f[l + 1][j]]);
          } else {
            st[x][i][j] = min(st[x][i][j], dist[seq[l + 1]][seq[l]][f[l + 1][j]][f[l][i]]);
          }
        }
      }
      /* if (l == r) {
        cout << "na " << l << '\n';
        for (int i = 0; i < st[x].size(); i++) {
          for (int j = 0; j < st[x][i].size(); j++) {
            cout << st[x][i][j] << " ";
          }
          cout << '\n';
        }
      } */
      return;
    }
    int mid = l + r >> 1;
    Build(x * 2, l, mid);
    Build(x * 2 + 1, mid + 1, r);
    Pull(x);
  };
  function<void(int, int, int, int)> Modify = [&](int x, int l, int r, int p) {
    if (l == r) {
      st[x].resize(f[l].size());
      for (int i = 0; i < f[l].size(); i++) {
        st[x][i] = vector<long long>(f[l + 1].size(), inf);
      }
      for (int i = 0; i < f[l].size(); i++) {
        for (int j = 0; j < f[l + 1].size(); j++) {
          if (seq[l] <= seq[l + 1]) {
            st[x][i][j] = min(st[x][i][j], dist[seq[l]][seq[l + 1]][f[l][i]][f[l + 1][j]]);
          } else {
            st[x][i][j] = min(st[x][i][j], dist[seq[l + 1]][seq[l]][f[l + 1][j]][f[l][i]]);
          }
        }
      }
      return;
    }
    int mid = l + r >> 1;
    if (p <= mid) {
      Modify(x * 2, l, mid, p);
    } else {
      Modify(x * 2 + 1, mid + 1, r, p);
    }
    Pull(x);
  };
  for (int i = 0; i < l; i++) {
    //Update(i);
  }
  //Build(1, 0, l - 2);
  auto Solve = [&]() {
    long long res = inf;
    for (int i = 0; i < st[1].size(); i++) {
      for (int j = 0; j < st[1][i].size(); j++) {
        res = min(res, st[1][i][j]);
      }
    }
    return (res == inf ? -1LL : res);
  };
  while (t--) {
    int p, x;
    cin >> p >> x;
    --p; --x;
    seq[p] = x;
    /* Update(p);
    if (p > 0) {
      Update(p - 1);
    }
    if (p + 1 < l) {
      Update(p + 1);
    }
    if (p + 1 < l) {
      Modify(1, 0, l - 2, p);
    }
    if (p + 2 < l) {
      Modify(1, 0, l - 2, p + 1);
    }
    if (p > 0) {
      Modify(1, 0, l - 2, p - 1);
    } */
    for (int i = 0; i < l; i++) {
      Update(i);
    }
    Build(1, 0, l - 2);
    cout << Solve() << '\n';
  }
  return 0;
}

Compilation message

wild_boar.cpp: In lambda function:
wild_boar.cpp:236:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  236 |       for (int i = 0; i < f[l].size(); i++) {
      |                       ~~^~~~~~~~~~~~~
wild_boar.cpp:239:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  239 |       for (int i = 0; i < f[l].size(); i++) {
      |                       ~~^~~~~~~~~~~~~
wild_boar.cpp:240:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  240 |         for (int j = 0; j < f[l + 1].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~~
wild_boar.cpp:259:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  259 |     int mid = l + r >> 1;
      |               ~~^~~
wild_boar.cpp: In lambda function:
wild_boar.cpp:267:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  267 |       for (int i = 0; i < f[l].size(); i++) {
      |                       ~~^~~~~~~~~~~~~
wild_boar.cpp:270:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  270 |       for (int i = 0; i < f[l].size(); i++) {
      |                       ~~^~~~~~~~~~~~~
wild_boar.cpp:271:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  271 |         for (int j = 0; j < f[l + 1].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~~
wild_boar.cpp:281:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  281 |     int mid = l + r >> 1;
      |               ~~^~~
wild_boar.cpp: In lambda function:
wild_boar.cpp:295:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  295 |     for (int i = 0; i < st[1].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~
wild_boar.cpp:296:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  296 |       for (int j = 0; j < st[1][i].size(); j++) {
      |                       ~~^~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 452 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 452 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 2 ms 604 KB Output is correct
27 Correct 132 ms 41184 KB Output is correct
28 Correct 129 ms 41296 KB Output is correct
29 Correct 338 ms 81124 KB Output is correct
30 Correct 426 ms 107816 KB Output is correct
31 Correct 356 ms 97016 KB Output is correct
32 Correct 363 ms 98188 KB Output is correct
33 Correct 289 ms 70056 KB Output is correct
34 Correct 312 ms 70012 KB Output is correct
35 Correct 378 ms 100432 KB Output is correct
36 Correct 595 ms 137044 KB Output is correct
37 Correct 308 ms 71764 KB Output is correct
38 Correct 265 ms 63824 KB Output is correct
39 Correct 490 ms 126080 KB Output is correct
40 Correct 278 ms 64384 KB Output is correct
41 Correct 265 ms 64456 KB Output is correct
42 Correct 342 ms 100248 KB Output is correct
43 Correct 259 ms 62248 KB Output is correct
44 Correct 285 ms 61912 KB Output is correct
45 Correct 229 ms 64084 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 452 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 2 ms 604 KB Output is correct
27 Correct 132 ms 41184 KB Output is correct
28 Correct 129 ms 41296 KB Output is correct
29 Correct 338 ms 81124 KB Output is correct
30 Correct 426 ms 107816 KB Output is correct
31 Correct 356 ms 97016 KB Output is correct
32 Correct 363 ms 98188 KB Output is correct
33 Correct 289 ms 70056 KB Output is correct
34 Correct 312 ms 70012 KB Output is correct
35 Correct 378 ms 100432 KB Output is correct
36 Correct 595 ms 137044 KB Output is correct
37 Correct 308 ms 71764 KB Output is correct
38 Correct 265 ms 63824 KB Output is correct
39 Correct 490 ms 126080 KB Output is correct
40 Correct 278 ms 64384 KB Output is correct
41 Correct 265 ms 64456 KB Output is correct
42 Correct 342 ms 100248 KB Output is correct
43 Correct 259 ms 62248 KB Output is correct
44 Correct 285 ms 61912 KB Output is correct
45 Correct 229 ms 64084 KB Output is correct
46 Correct 171 ms 16124 KB Output is correct
47 Correct 3413 ms 286424 KB Output is correct
48 Correct 3624 ms 387188 KB Output is correct
49 Correct 4126 ms 492512 KB Output is correct
50 Correct 3721 ms 467392 KB Output is correct
51 Correct 3572 ms 433076 KB Output is correct
52 Correct 3744 ms 402092 KB Output is correct
53 Correct 3686 ms 401796 KB Output is correct
54 Correct 3700 ms 401620 KB Output is correct
55 Correct 3727 ms 399764 KB Output is correct
56 Correct 3831 ms 443684 KB Output is correct
57 Correct 4000 ms 492256 KB Output is correct
58 Correct 4149 ms 539832 KB Output is correct
59 Correct 4364 ms 592300 KB Output is correct
60 Correct 4558 ms 647408 KB Output is correct
61 Correct 4614 ms 707148 KB Output is correct
62 Correct 4871 ms 772348 KB Output is correct
63 Correct 4899 ms 840692 KB Output is correct
64 Correct 3334 ms 997604 KB Output is correct
65 Correct 3350 ms 997708 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 452 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 2 ms 604 KB Output is correct
27 Correct 132 ms 41184 KB Output is correct
28 Correct 129 ms 41296 KB Output is correct
29 Correct 338 ms 81124 KB Output is correct
30 Correct 426 ms 107816 KB Output is correct
31 Correct 356 ms 97016 KB Output is correct
32 Correct 363 ms 98188 KB Output is correct
33 Correct 289 ms 70056 KB Output is correct
34 Correct 312 ms 70012 KB Output is correct
35 Correct 378 ms 100432 KB Output is correct
36 Correct 595 ms 137044 KB Output is correct
37 Correct 308 ms 71764 KB Output is correct
38 Correct 265 ms 63824 KB Output is correct
39 Correct 490 ms 126080 KB Output is correct
40 Correct 278 ms 64384 KB Output is correct
41 Correct 265 ms 64456 KB Output is correct
42 Correct 342 ms 100248 KB Output is correct
43 Correct 259 ms 62248 KB Output is correct
44 Correct 285 ms 61912 KB Output is correct
45 Correct 229 ms 64084 KB Output is correct
46 Correct 171 ms 16124 KB Output is correct
47 Correct 3413 ms 286424 KB Output is correct
48 Correct 3624 ms 387188 KB Output is correct
49 Correct 4126 ms 492512 KB Output is correct
50 Correct 3721 ms 467392 KB Output is correct
51 Correct 3572 ms 433076 KB Output is correct
52 Correct 3744 ms 402092 KB Output is correct
53 Correct 3686 ms 401796 KB Output is correct
54 Correct 3700 ms 401620 KB Output is correct
55 Correct 3727 ms 399764 KB Output is correct
56 Correct 3831 ms 443684 KB Output is correct
57 Correct 4000 ms 492256 KB Output is correct
58 Correct 4149 ms 539832 KB Output is correct
59 Correct 4364 ms 592300 KB Output is correct
60 Correct 4558 ms 647408 KB Output is correct
61 Correct 4614 ms 707148 KB Output is correct
62 Correct 4871 ms 772348 KB Output is correct
63 Correct 4899 ms 840692 KB Output is correct
64 Correct 3334 ms 997604 KB Output is correct
65 Correct 3350 ms 997708 KB Output is correct
66 Correct 6553 ms 63704 KB Output is correct
67 Correct 2727 ms 242308 KB Output is correct
68 Correct 2780 ms 960536 KB Output is correct
69 Correct 4985 ms 961600 KB Output is correct
70 Execution timed out 18163 ms 997972 KB Time limit exceeded
71 Halted 0 ms 0 KB -