Submission #1006789

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006789		NeroZein	Closing Time (IOI23_closing)	C++17	0 / 100	41 ms	10344 KiB

closing

#include "closing.h"

#include <bits/stdc++.h>
using namespace std; 

const int N = 5003;
const long long INF = 1e16;

using pli = pair<long long, int>;

int n, x, y;
long long k;
long long dist[2][N];
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); 
      }
    }
  }
}

int check(int mask, int v, int p) {
  if (!(mask >> v & 1)) {
    return 0; 
  }
  int ret = 1; 
  for (auto [u, w] : g[v]) {
    if (u == p) continue;
    ret += check(mask, u, v); 
  }
  return ret; 
}

int dfs(int v, int p, int mask, long long& sum, vector<int>& unused) {
  int ret = (v == x ? 0 : v == y ? 1 : -1); 
  for (auto [u, w] : g[v]) {
    if (u == p || (mask >> u & 1)) continue; 
    int uret = dfs(u, v, mask, sum, unused); 
      //if (mask == 2) {
        //cout << v << ' ' << u << ' ' << uret << endl; 
      //}
    if (uret != -1) {
      if (ret == -1) {
        ret = uret;        
      }
      sum += dist[uret][u];
      //assert(dist[uret][u] <= dist[!uret][u]);
    }
  }
  if (v != p && ret == -1) {
    unused.push_back(v); 
  }
  return ret; 
}

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]);
  }
  int ans = 0; 
  dijkstra(0, x);
  dijkstra(1, y);
  for (int mask = 0; mask < (1 << n); ++mask) {
    int tmp = 2;
    bool ok = true; 
    for (int j = 0; j < n; ++j) {
      if (mask >> j & 1) {
        int cnt = __builtin_popcount(mask);
        tmp += cnt * 2; 
        ok = check(mask, j, j) == cnt;
        break; 
      }
    }
    if (!ok) {
      //cout << "BadMask: " << mask << endl; 
      continue; 
    }
    vector<int> unused; 
    if (mask == 0) {
      for (int j = 0; j < n; ++j) {
        if (j != x && j != y) {
          unused.push_back(j); 
        }
      }
    }
    long long sum = 0; 
    for (int j = 0; j < n; ++j) {
      if (!(mask >> j & 1)) continue; 
      sum += max(dist[0][j], dist[1][j]);
      dfs(j, j, mask, sum, unused);
    }
    if (sum > k) {
      continue; 
    }
    sort(unused.begin(), unused.end(), [&](int i, int j) {
      return min(dist[0][i], dist[1][i]) < min(dist[0][j], dist[1][j]);
    });
    {
      //cout << "Mask: " << mask << ' ' << "Sum: " << sum << ' ' << tmp << ' ' << "Unused:\n";
      //for (int j : unused) {
        //cout << j << ' ' << min(dist[0][j], dist[1][j]) << '\n';
      //}
      //cout << endl; 
    }
    for (int j : unused) {
      if (sum + min(dist[0][j], dist[1][j]) <= k) {
        tmp++;
        sum += min(dist[0][j], dist[1][j]);
      } else {
        break; 
      }
    }
    //cout << "mask, tmp: " << mask << ' ' << tmp << endl; 
    ans = max(ans, tmp);
  }
  for (int i = 0; i < n; ++i) {
    g[i].clear(); 
  }
  return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 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