oj.uz

Submission #840569

# Submission time Handle Problem Language Result Execution time Memory
840569 2023-08-31T13:53:18 Z bicsi Closing Time (IOI23_closing) C++17
17 / 100
 113 ms 26476 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]);
  }
  vector<int> parent(N, -1);
  auto precomp = [&](int src) {
    vector<int> q = {src};
    vector<long long> ret(N, -1);
    parent[src] = -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);
          parent[vec] = node;
        }
      }
    }
    return ret;
  };

  vector<vector<long long>> dist = {precomp(X), precomp(Y)};
  
  vector<int> path;
  for (int node = X; node != -1; node = parent[node]) 
    path.push_back(node);
  
  // for (auto node : path) cerr << node << " ";
  // cerr << endl;

  int best = 0;
  
  for (int phase = 0; phase < 2; ++phase) {
    long long _K = K;
    vector<vector<int>> taken = {vector<int>(N, 0), vector<int>(N, 0)};
    vector<vector<int>> seen = {vector<int>(N, 0), vector<int>(N, 0)};
    priority_queue<tuple<long long, int, int>> pq;
    auto push = [&](int z, int node) {
      if (seen[z][node]) return;
      seen[z][node] = true;
      pq.emplace(-2 * dist[z][node], z, node);
      if (phase == 1 && seen[!z][node]) {
        pq.emplace(-(dist[z][node] + dist[!z][node]), 3, node);
      }
    };
    
    vector<pair<int, int>> nxt;

    auto take = [&](int z, int node) {
      if (taken[z][node]) return true;
      long long d = dist[z][node];
      if (taken[!z][node]) d = max(0LL, d - dist[!z][node]);
      //cerr << "try take: " << node << " d=" << d << endl;
      if (d > K) return false;
      K -= d;
      taken[z][node] = true;
      for (auto [vec, _] : graph[node])
        nxt.emplace_back(z, vec);
      //cerr << "ok" << endl;
      return true;
    };

    if (phase == 1) {
      for (auto node : path) {
        if (dist[0][node] < dist[1][node]) take(0, node);
        else take(1, node);
      }
    } else {
      take(0, X); take(1, Y);
    }

    for (auto [z, vec] : nxt) push(z, vec);
    nxt.clear();

    while (pq.size()) {
      auto [_, z, node] = pq.top(); pq.pop();
      if (z == 3) {
        long long oldK = K;
        int oldTake[2] = {taken[0][node], taken[1][node]};
        if (!take(0, node) || !take(1, node)) {
          K = oldK;
          taken[0][node] = oldTake[0];
          taken[1][node] = oldTake[1];
          nxt.clear();
        }
      } else {
        take(z, node);
      }
      for (auto [z, vec] : nxt)
        push(z, vec);
      nxt.clear();
    }
    int ans = 0;
    for (int z = 0; z < 2; ++z) 
      for (int i = 0; i < N; ++i)
        ans += taken[z][i];
    best = max(best, ans);
    K = _K;
  }
  return best;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 26476 KB Output is correct
2 Correct 113 ms 26096 KB Output is correct
3 Correct 80 ms 2784 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Correct 0 ms 212 KB Output is correct
8 Correct 0 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 0 ms 212 KB Output is correct

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Correct 0 ms 212 KB Output is correct
8 Correct 0 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 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 0 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 Incorrect 1 ms 212 KB 2nd lines differ - on the 1st token, expected: '25', found: '24'
19 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 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 Correct 0 ms 212 KB Output is correct
8 Correct 0 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 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 0 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 Incorrect 1 ms 212 KB 2nd lines differ - on the 1st token, expected: '25', found: '24'
19 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 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 Incorrect 0 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 256 KB Output is correct
2 Correct 1 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 1 ms 212 KB Output is correct
8 Correct 0 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 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 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 0 ms 212 KB Output is correct
19 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
20 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 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 1 ms 212 KB Output is correct
8 Correct 0 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 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 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 0 ms 212 KB Output is correct
19 Incorrect 1 ms 212 KB 2nd lines differ - on the 1st token, expected: '25', found: '24'
20 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 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 1 ms 212 KB Output is correct
8 Correct 0 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 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 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 0 ms 212 KB Output is correct
19 Incorrect 1 ms 212 KB 2nd lines differ - on the 1st token, expected: '25', found: '24'
20 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 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 1 ms 212 KB Output is correct
8 Correct 0 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 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 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 0 ms 212 KB Output is correct
19 Incorrect 1 ms 212 KB 2nd lines differ - on the 1st token, expected: '25', found: '24'
20 Halted 0 ms 0 KB -