Submission #1101486

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101486		VinhLuu	Road Closures (APIO21_roads)	C++17	Compilation error	0 ms	0 KiB

roads

#include <bits/stdc++.h>
#define int 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], kq[N], g[N], d[N], T[N], deg[N];

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

int f[2][N];

void add(int u,int w,int 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<int> tmp, undo;
  int 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)){
    int 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)){
    int 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<int> ver[N];

vector<int> 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++;
    }
    int 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<int> _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(long long int, std::vector<long long int>, std::vector<long long int>, std::vector<long long int>)':
roads.cpp:87:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     while(ptr < e.size() && deg[e[ptr]] == k){
      |           ~~~~^~~~~~~~~~
roads.cpp:77:7: warning: unused variable '_max' [-Wunused-variable]
   77 |   int _max = 0;
      |       ^~~~
/usr/bin/ld: /tmp/ccZN53QH.o: in function `main':
grader.cpp:(.text.startup+0x277): undefined reference to `minimum_closure_costs(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status