oj.uz

Submission #839852

# Submission time Handle Problem Language Result Execution time Memory
839852 2023-08-30T18:53:15 Z bicsi Closing Time (IOI23_closing) C++17
8 / 100
 97 ms 25368 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<int> xy = {X, Y};
  vector<vector<long long>> dist = {precomp(X), precomp(Y)};
  vector<vector<int>> taken = {vector<int>(N, 0), vector<int>(N, 0)};
  priority_queue<tuple<long long, int, int>> pq;
  auto push = [&](int z, int node) {
    long long d = dist[z][node];
    if (taken[z][node]) return;
    pq.emplace(-d, z, node);
  };

  push(0, xy[0]); push(1, xy[1]);
  int ans = 0;
  while (pq.size()) {
    auto [_, z, node] = pq.top(); pq.pop();
    long long d = dist[z][node];
    if (taken[!z][node]) d = max(0LL, d - dist[!z][node]);
    if (d > K) break;
    K -= d; ++ans;
    taken[z][node] = true;
    for (auto [vec, _] : graph[node]) 
      push(z, vec);
  }
  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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 23460 KB Output is correct
2 Correct 97 ms 25368 KB Output is correct
3 Correct 62 ms 4780 KB Output is correct

Subtask #2
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 1 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 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '96', found: '93'
7 Halted 0 ms 0 KB -

Subtask #3
0.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 1 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 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '96', found: '93'
7 Halted 0 ms 0 KB -

Subtask #4
0.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 1 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 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '96', found: '93'
7 Halted 0 ms 0 KB -

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 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
8 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 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '96', found: '93'
8 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 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '96', found: '93'
8 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 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '96', found: '93'
8 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 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '96', found: '93'
8 Halted 0 ms 0 KB -