oj.uz

Submission #1007309

# Submission time Handle Problem Language Result Execution time Memory
1007309 2024-06-24T15:09:31 Z NeroZein Closing Time (IOI23_closing) C++17
8 / 100
 95 ms 24620 KB 
#include "closing.h"
#include <bits/stdc++.h>

using namespace std; 

const int N = 2e5 + 5;
const long long INF = 1e18 + 18; 

using pli = pair<long long, int>; 

int n, x, y;
long long k; 
long long dist[2][N];
//long long dp[N][N * 2][6]; 
vector<pair<int, int>> g[N];
 
void dijkstra(int ver, int src) {
  for (int i = 0; i < n; ++i) {
    dist[ver][i] = INF;
  }
  dist[ver][src] = 0;
  priority_queue<pli, vector<pli>, greater<pli>> pq; 
  pq.emplace(0, src); 
  while (!pq.empty()) {
    auto [c, v] = pq.top();
    pq.pop();
    if (c != dist[ver][v]) {
      continue; 
    }
    for (auto [u, w] : g[v]) {
      if (c + w < dist[ver][u]) {
        dist[ver][u] = c + w; 
        pq.emplace(dist[ver][u], u); 
      }
    }
  }
}

void init() {
  for (int i = 0; i < n; ++i) {
    g[i].clear();
  }
}

int max_score(int N_, int X_, int Y_, long long K_, vector<int> U, vector<int> V, vector<int> W) {
  n = N_, x = X_, y = Y_, k = K_; 
  for (int i = 0; i < n - 1; ++i) {
    g[U[i]].emplace_back(V[i], W[i]);
    g[V[i]].emplace_back(U[i], W[i]);
  }
  //for (int i = 0; i <= n; ++i) {
    //for (int j = 0; j <= n * 2; ++j) {
      //for (int l = 0; l < 6; ++l) {
        //dp[i][j][l] = INF;
      //}
    //}
  //}
  dijkstra(0, x);
  dijkstra(1, y);
  vector<int> ord(n);
  iota(ord.begin(), ord.end(), 0);
  sort(ord.begin(), ord.end(), [&](int i, int j) {
    return min(dist[0][i], dist[1][i]) < min(dist[0][j], dist[1][j]);
  });
  int tmp = 0;
  long long sum = 0; 
  for (int i = 0; i < n; ++i) {
    if (sum + min(dist[0][ord[i]], dist[1][ord[i]]) <= k) {
      sum += min(dist[0][ord[i]], dist[1][ord[i]]);
      tmp++; 
    }
  }
  //dp[0][0][0] = 0;
  //for (int i = 0; i < n; ++i) {
    //for (int curans = 0; curans < n * 2; ++curans) {
      //for (int f = 0; f < 5; ++f) {//0 nothing, 1 x, 2 xy, 3 y, 4 nothing
        //dp[i][curans][f + 1] = min(dp[i][curans][f + 1], dp[i][curans][f]);
        //if (i == x && f != 1 && f != 2) continue;
        //if (i == y && f != 2 && f != 3) continue; 
        //if (f == 2) {
          //dp[i + 1][curans + 2][f] = min(dp[i + 1][curans + 2][f], dp[i][curans][f] + max(dist[0][i], dist[1][i]));
        //} else if (f == 0 || f == 4) {
          //dp[i + 1][curans][f] = min(dp[i + 1][curans][f], dp[i][curans][f]);
        //} else {
          //dp[i + 1][curans + 1][f] = min(dp[i + 1][curans + 1][f], dp[i][curans][f] + dist[f / 2][i]);
        //}
      //}
    //}
  //}
  int ans = 0; 
  //for (int curans = 0; curans <= 2 * n; ++curans) {
    //for (int j = 0; j <= 4; ++j) {
      //if (dp[n][curans][j] <= k) {
        //ans = max(ans, curans);
      //}      
    //}
  //}
  ans = max(ans, tmp); 
  init();
  return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4952 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 24620 KB Output is correct
2 Correct 91 ms 24372 KB Output is correct
3 Correct 50 ms 10064 KB Output is correct

Subtask #2
0.0 / 9.0

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

Subtask #3
0.0 / 12.0

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

Subtask #4
0.0 / 14.0

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

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4952 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4952 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4952 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4952 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4952 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -