oj.uz

Submission #840625

# Submission time Handle Problem Language Result Execution time Memory
840625 2023-08-31T14:38:08 Z bicsi Closing Time (IOI23_closing) C++17
35 / 100
 1000 ms 33188 KB 
#include "closing.h"

#include <bits/stdc++.h>

using namespace std;

int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
  vector<vector<pair<int, int>>> graph(N);
  for (int i = 0; i < (int)U.size(); ++i) {
    graph[U[i]].emplace_back(V[i], W[i]);
    graph[V[i]].emplace_back(U[i], W[i]);
  }
  auto precomp = [&](int src) {
    vector<int> q = {src};
    vector<long long> ret(N, -1);
    ret[src] = 0;
    for (int i = 0; i < N; ++i) {
      int node = q[i];
      for (auto [vec, cost] : graph[node]) {
        if (ret[vec] == -1) {
          ret[vec] = ret[node] + cost;
          q.push_back(vec);
        }
      }
    }
    return ret;
  };

  vector<vector<long long>> dist = {precomp(X), precomp(Y)};
  
  auto try_indep = [&]() {
    vector<long long> v;
    for (int z = 0; z < 2; ++z)
      for (int i = 0; i < N; ++i)
        v.push_back(dist[z][i]);
    sort(v.begin(), v.end());
    long long rem = K;
    int ans = 0;
    for (auto x : v) {
      if (x <= rem) rem -= x, ans += 1;
    }
    return ans;
  };

  auto try_dep = [&](int root) {
    long long rem = K;
    vector<tuple<long long, int, int>> v;
    vector<vector<bool>> taken(2, vector<bool>(N, false));
    int ans = 0;
    for (int i = 0; i < N; ++i) {
      long long a = dist[0][i], b = dist[1][i];
      if (i == root) {
        taken[0][i] = taken[1][i] = true;
        rem -= max(a, b);
        ans += 2;
      } else if (a + b == dist[0][Y]) {
        if (a < b) {
          // v.emplace_back(2 * a, i, 0);
          rem -= a; taken[0][i] = true;
          v.emplace_back(2 * (b - a), i, 1);
          ans += 1;
        } else {
          rem -= b; taken[1][i] = true;
          v.emplace_back(2 * (a - b), i, 0);
          // v.emplace_back(2 * b, i, 1);
          ans += 1;
        }
      } else {
        if (a < b) {
          if (2 * a <= b) v.emplace_back(2 * a, i, 0), v.emplace_back(2 * (b - a), i, 1);
          else v.emplace_back(b, i, 2);
        } else {
          if (2 * b <= a) v.emplace_back(2 * b, i, 1), v.emplace_back(2 * (a - b), i, 0);
          else v.emplace_back(a, i, 2);
        }
      }
    }

    if (rem < 0) return 0;

    sort(v.begin(), v.end());
    for (auto [c, i, z] : v) {
      if (z != 2) c /= 2;
      if (c > rem) break;
      rem -= c;
      ans += (z == 2 ? 2 : 1);
      // cerr << "take: " << i << " " << z << endl;
      if (z == 2) {
        assert(taken[0][i] == 0 && taken[1][i] == 0);
        taken[0][i] = 1;
        taken[1][i] = 1;
      } else {
        assert(taken[z][i] == 0);
        taken[z][i] = 1;
      }
    }

    for (int z = 0; z < 2; ++z) {
      for (int i = 0; i < N; ++i) {
        if (taken[z][i] == 0 && dist[z][i] <= rem) {
          return ans + 1;
        }
      }
    }
    return ans;
  };

  int ans = try_indep();
  for (int root = 0; root < N; ++root) {
    if (dist[0][root] + dist[1][root] != dist[0][Y]) continue;
    ans = max(ans, try_dep(root));
  }
  return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1042 ms 33188 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 5 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 3 ms 340 KB Output is correct
24 Correct 2 ms 340 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 5 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 3 ms 340 KB Output is correct
24 Correct 2 ms 340 KB Output is correct
25 Correct 3 ms 212 KB Output is correct
26 Correct 2 ms 596 KB Output is correct
27 Correct 2 ms 596 KB Output is correct
28 Correct 381 ms 664 KB Output is correct
29 Correct 243 ms 596 KB Output is correct
30 Correct 8 ms 596 KB Output is correct
31 Correct 46 ms 688 KB Output is correct
32 Correct 45 ms 684 KB Output is correct

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '9', found: '8'
10 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 256 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '9', found: '8'
22 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 256 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 5 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 3 ms 340 KB Output is correct
25 Correct 2 ms 340 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '9', found: '8'
29 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 256 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 5 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 3 ms 340 KB Output is correct
25 Correct 2 ms 340 KB Output is correct
26 Correct 3 ms 212 KB Output is correct
27 Correct 2 ms 596 KB Output is correct
28 Correct 2 ms 596 KB Output is correct
29 Correct 381 ms 664 KB Output is correct
30 Correct 243 ms 596 KB Output is correct
31 Correct 8 ms 596 KB Output is correct
32 Correct 46 ms 688 KB Output is correct
33 Correct 45 ms 684 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 0 ms 212 KB Output is correct
36 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '9', found: '8'
37 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 256 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 5 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 3 ms 340 KB Output is correct
25 Correct 2 ms 340 KB Output is correct
26 Correct 3 ms 212 KB Output is correct
27 Correct 2 ms 596 KB Output is correct
28 Correct 2 ms 596 KB Output is correct
29 Correct 381 ms 664 KB Output is correct
30 Correct 243 ms 596 KB Output is correct
31 Correct 8 ms 596 KB Output is correct
32 Correct 46 ms 688 KB Output is correct
33 Correct 45 ms 684 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 0 ms 212 KB Output is correct
36 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '9', found: '8'
37 Halted 0 ms 0 KB -