oj.uz

Submission #840156

# Submission time Handle Problem Language Result Execution time Memory
840156 2023-08-31T07:27:25 Z two_sides Closing Time (IOI23_closing) C++17
8 / 100
 285 ms 39076 KB 
#include <bits/stdc++.h>

namespace {
  using namespace std;
  
  int n, x, y;
  long long lim;
  vector<vector<pair<int, int>>> adj;
  vector<long long> dx, dy;
  
  void dfs(int u, int p, vector<long long> &d) {
    for (auto [v, w] : adj[u])
      if (v != p) {
        d[v] = d[u] + w; dfs(v, u, d);
      }
  }
  
  struct comp {
    bool operator () (int i, int j) const {
      return dx[i] < dx[j] || (dx[i] == dx[j] && i < j);
    }
  };
}

int max_score(int N, int X, int Y, long long LIM,
vector<int> U, vector<int> V, vector<int> W) {
  n = N; x = X; y = Y; lim = LIM;
  
  adj.resize(n); dx.resize(n); dy.resize(n);
  for (int i = 0; i < n; i++) {
    adj[i].clear(); dx[i] = dy[i] = 0;
  }
  for (int i = 0; i + 1 < n; i++) {
    adj[U[i]].emplace_back(V[i], W[i]);
    adj[V[i]].emplace_back(U[i], W[i]);
  }
  
  dfs(x, -1, dx); dfs(y, -1, dy);
  
  vector<int> sorted(n);
  iota(sorted.begin(), sorted.end(), 0);
  for (int i = 0; i < n; i++)
    if (dx[i] > dy[i]) swap(dx[i], dy[i]);
  sort(sorted.begin(), sorted.end(), [&](int i, int j) {
    return dy[i] < dy[j];
  });
  set<int, comp> alive, removed;
  long long sum = 0;
  for (int i = 0; i < n; i++) {
    alive.insert(i); sum += dx[i];
  }
  
  
  while (sum > lim) {
    int i = *alive.rbegin();
    sum -= dx[i];
    removed.insert(i);
    alive.erase(i);
  }
  
  int res = alive.size(), cur = 0;


  for (int i : sorted) {
    if (alive.erase(i)) sum -= dx[i];
    else removed.insert(i);
    sum += dy[i]; cur += 2;
    while (sum > lim && alive.size()) {
      int j = *alive.rbegin();
      sum -= dx[j];
      removed.insert(j);
      alive.erase(j);
    }
    while (sum < lim && removed.size()) {
      int j = *removed.begin();
      if (sum + dx[j] > lim) break;
      sum += dx[j];
      alive.insert(j);
      removed.erase(j);
    }
    if (sum <= lim)
      res = max(res, cur + int(alive.size()));
  }
  return res;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 34704 KB Output is correct
2 Correct 285 ms 39076 KB Output is correct
3 Correct 121 ms 2900 KB Output is correct

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 260 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 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '3', found: '4'
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 260 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 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '3', found: '4'
6 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 260 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 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '3', found: '4'
6 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

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

Subtask #6
0.0 / 11.0

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

Subtask #7
0.0 / 10.0

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

Subtask #8
0.0 / 10.0

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

Subtask #9
0.0 / 17.0

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