Submission #1101494

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101494		VinhLuu	Road Closures (APIO21_roads)	C++17	100 / 100	166 ms	53248 KiB

roads

#include <bits/stdc++.h>
#define ll long long
#define all(vin) vin.begin(), vin.end()
using namespace std;

typedef pair<int,int> pii;
const int N = 2e5 + 2;

int n, A[N], B[N], C[N],  deg[N];
ll kq[N], g[N], d[N], T[N];

multiset<ll> st[N];
vector<pair<int,int>> p[N];
vector<int> vr;

ll f[2][N];

void add(int u,ll w,ll type){
  g[u] += type * w;
  if(type == 1){
    st[u].insert(w);
  }else{
    auto fin = st[u].find(w);
    st[u].erase(fin);
  }
}

void dfs(int u){
  vector<ll> tmp, undo;
  ll k = T[u], de = deg[u] - k, sum = 0;
  while((int)st[u].size() > max(0ll, de)) add(u, (*st[u].rbegin()), -1);
  for(auto [j, w] : p[u]) if(T[j] != k){
    if(deg[j] <= k) break;
    T[j] = k;
    dfs(j);
    if(f[0][j] + w <= f[1][j]){
      sum += f[0][j] + w;
      de--;
    }else{
      sum += f[1][j];
      tmp.push_back(f[0][j] + w - f[1][j]);
      add(u, f[0][j] + w - f[1][j], 1);
    }
  }
  while((int)st[u].size() > max(0ll, de)){
    ll val = (*st[u].rbegin());
    undo.push_back(val);
    add(u, val, -1);
  }
  f[1][u] = sum + g[u];
  while((int)st[u].size() > max(0ll, de - 1)){
    ll val = (*st[u].rbegin());
    undo.push_back(val);
    add(u, val, -1);
  }
  f[0][u] = sum + g[u];
  for(auto j : undo) add(u, j, 1);
  for(auto j : tmp) add(u, j, -1);
}

vector<ll> ver[N];

vector<ll> minimum_closure_costs(int _n, vector<int> _u, vector<int> _v, vector<int> _c){
  n = _n;
  for(int i = 1; i < n; i ++){
    int u = _u[i - 1] + 1;
    int v = _v[i - 1] + 1;
    int c = _c[i - 1];
    A[i] = u;
    B[i] = v;
    C[i] = c;
    kq[0] += c;
    deg[u]++;
    deg[v]++;
    p[u].push_back({v, c});
    p[v].push_back({u, c});
  }
  int _max = 0;
  vector<int> e;
  for(int i = 1; i <= n; i ++){
    ver[deg[i]].push_back(i);
    e.push_back(i);
  }
  for(int i = 1; i <= n; i ++) sort(all(p[i]), [&](pii x, pii y){return deg[x.first] > deg[y.first];});
  sort(all(e), [&](int x,int y){return deg[x] < deg[y];});
  int ptr = 0;
  for(int k = 1; k < n; k ++){
    while(ptr < e.size() && deg[e[ptr]] == k){
      int pos = e[ptr];
      for(auto [j, w] : p[pos]) if(deg[j] > k) add(j, w, 1);
      ptr++;
    }
    ll ans = 0;
    for(int i = ptr; i < (int)e.size(); i ++) if(T[e[i]] != k){
      T[e[i]] = k;
      dfs(e[i]);
      ans += f[1][e[i]];
    }
    kq[k] = ans;
  }

  vector<ll> _return;
  for(int i = 0; i < n; i ++) _return.push_back(kq[i]);
  return _return;

}

Compilation message (stderr)

roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:88:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     while(ptr < e.size() && deg[e[ptr]] == k){
      |           ~~~~^~~~~~~~~~
roads.cpp:78:7: warning: unused variable '_max' [-Wunused-variable]
   78 |   int _max = 0;
      |       ^~~~

• 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