제출 #840156

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
840156		two_sides	봉쇄 시간 (IOI23_closing)	C++17	8 / 100	285 ms	39076 KiB

closing

#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
• Subtask 1: 8 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17