Submission #1202832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202832		aykhn	Road Closures (APIO21_roads)	C++20	100 / 100	254 ms	75764 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>

using namespace std;

#define inf 1000000000000

const int MXN = 1e5 + 5;

struct BIT
{
  int n;
  vector<long long> ft;
  void init(int N)
  {
    n = N + 5;
    ft.assign(n + 5, 0);
  }
  void add(int pos, long long val)
  {
    for (; pos <= n; pos += pos & -pos) ft[pos] += 1LL * val;
  }
  long long get(int pos, long long res = 0)
  {
    for (; pos > 0; pos -= pos & -pos) res += ft[pos];
    return res;
  }
};

int n, K;
vector<array<long long, 2>> adj[MXN];
set<array<long long, 2>> g[MXN];
int used[MXN];
BIT cnt[MXN], sum[MXN];

void unlock(int node, int idx)
{
  cnt[node].add(idx + 1, 1);
  sum[node].add(idx + 1, adj[node][idx][0]);
}
long long sumk(int node, int k)
{
  if (k < 0) return -inf;
  int sz = adj[node].size();
  long long cur = 0, curs = 0;
  for (int i = 20; i >= 0; i--)
  {
    if ((cur | (1 << i)) > sz) continue;
    if (cnt[node].ft[cur | (1 << i)] <= k)
    {
      k -= cnt[node].ft[cur | (1 << i)];
      curs += sum[node].ft[cur | (1 << i)];
      cur |= (1 << i);
    }
  }
  return curs;
}
array<long long, 2> dfs(int a)
{
  used[a] = 1;
  array<long long, 2> res = {0, 0};
  long long S = 0;
  vector<long long> o;
  for (auto [w, v] : g[a])
  {
    if (used[v]) continue;
    array<long long, 2> x = dfs(v);
    S += x[0];
    o.push_back(x[1] + w - x[0]);
  }
  sort(o.rbegin(), o.rend());
  res[0] = sumk(a, K) + S, res[1] = sumk(a, K - 1) + S;
  long long cnt = K, curS = 0;
  for (long long &val : o)
  {
    curS += val;
    cnt--;
    res[0] = max(res[0], S + curS + sumk(a, cnt));
    res[1] = max(res[1], S + curS + sumk(a, cnt - 1));
  }
  return res;
}


vector<long long> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) 
{
  n = N;
  long long all = 0;
  for (int i = 0; i < U.size(); i++)
  {
    long long u = U[i], v = V[i], w = W[i];
    adj[u].push_back({w, v});
    adj[v].push_back({w, u});
    g[u].insert({w, v});
    g[v].insert({w, u});
    all += w;
  }
  for (int i = 0; i < N; i++) 
  {
    sort(adj[i].rbegin(), adj[i].rend());
  }
  for (int i = 0; i < N; i++)
  {
    cnt[i].init(adj[i].size());
    sum[i].init(adj[i].size());
  }
  vector<array<long long, 2>> ed;
  vector<array<long long, 5>> q;
  for (int i = 0; i < U.size(); i++)
  {
    long long u = U[i], v = V[i], w = W[i];
    if (adj[u].size() > adj[v].size()) swap(u, v);
    ed.push_back({(long long)adj[v].size(), w});
    int lx = 0, rx = (int)adj[v].size() - 1;
    while (lx < rx)
    {
      int mid = (lx + rx) >> 1;
      if (adj[v][mid] > array<long long, 2>{w, u}) lx = mid + 1;
      else rx = mid;
    }
    q.push_back({(long long)adj[u].size(), u, v, w, lx});
  }
  sort(ed.begin(), ed.end());
  sort(q.begin(), q.end());
  int o[n];
  iota(o, o + n, 0);
  sort(o, o + n, [&](int x, int y)
  {
    return adj[x].size() > adj[y].size();
  });
  vector<long long> ans;
  for (long long k = 0, i = 0, j = 0, alr = 0; k < n; k++)
  {
    K = k;
    while (i < ed.size() && ed[i][0] <= k) alr += ed[i][1], i++;
    while (j < q.size() && q[j][0] <= k)
    {
      int u = q[j][1], v = q[j][2], w = q[j][3], idx = q[j][4];
      unlock(v, idx);
      g[v].erase({w, u});
      j++;
    }
    long long res = 0;
    for (int &i  : o)
    {
      if (adj[i].size() <= k) break;
      used[i] = 0;
    }
    for (int &i : o)
    {
      if (adj[i].size() <= k) break;
      if (used[i]) continue;
      array<long long, 2> x = dfs(i);
      res += max(x[0], x[1]);
    }
    ans.push_back(all - (res + alr));
  }
  return ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 14 / 14
• Subtask 4: 10 / 10
• Subtask 5: 17 / 17
• Subtask 6: 25 / 25
• Subtask 7: 22 / 22