oj.uz

Submission #840620

# Submission time Handle Problem Language Result Execution time Memory
840620 2023-08-31T14:32:41 Z bicsi Closing Time (IOI23_closing) C++17
8 / 100
 120 ms 32572 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 = [&]() {
    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 (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(a + 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 + b, 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;
  };

  long long indep = try_indep();
  long long dep = try_dep();
  cerr << indep << " " << dep << endl;
  return max(indep, dep);
}

Subtask #0
0.0 / 0.0

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 32572 KB Output is correct
2 Correct 120 ms 27680 KB Output is correct
3 Correct 79 ms 2728 KB Output is correct

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '30', found: '25'
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '30', found: '25'
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '30', found: '25'
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

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

Subtask #6
0.0 / 11.0

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

Subtask #7
0.0 / 10.0

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

Subtask #8
0.0 / 10.0

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

Subtask #9
0.0 / 17.0

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