Submission #720307

#	Time	Username	Problem	Language	Result	Execution time	Memory
720307		Username4132	Road Closures (APIO21_roads)	C++14	12 / 100	268 ms	76332 KiB

roads

#include "roads.h"
#include<vector>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)
#define dforsn(i, s, n) for(int i=n-1; i>=s; --i)
#define PB push_back
#define MP make_pair
#define F first
#define S second

const int MAXN=100010;
vector<pii> g[MAXN], lim[MAXN];
vector<int> deg[MAXN];
vector<pair<int, pii>> ar[MAXN];
int vert[MAXN], dep[MAXN], par[MAXN];
bool vis[MAXN];
ll parCost[MAXN];

auto cmp = [](int a, int b){return dep[a]<dep[b];};
set<int, decltype(cmp)> deps(cmp);

struct node{
  map<int, ll> cost;
  set<pli> fst;
  set<pli>::iterator itr;
  int pos=0;
  ll sum=0;
  node(int v, int p){
    for(auto to:g[v]) if(to.F!=p){
      cost[to.F]=to.S;
      fst.insert(MP(to.S, to.F));
    }
    itr=fst.begin();
  }
  node(){}

  void insert(pii pa){
    auto it = fst.insert(pa).F;
    if(itr==fst.end() || *it<*itr){
      itr = prev(itr);
      sum+=it->F-itr->F;
    }
  }

  void erase(set<pli>::iterator it){
    if(itr==fst.end() || *it<=*itr){
      sum+=itr->F-it->F;
      itr = next(itr);
    }
    fst.erase(it);
  }

  void update(int to, ll value){
    ll cst = cost[to];
    if(cst==value) return;
    auto it = fst.find(MP(cst, to));
    insert(MP(value, to));
    erase(it);
    cost[to]=value;
  }

  void incr(){
    pos++;
    sum+=itr->F;
    itr=next(itr);
  }

  
  ll find_sum(int ind){
    while(pos<ind) incr();
    return sum;
  }
};


int n, stat=0;
node info[MAXN];

void dfs_cons(int v, int p){
  for(auto to:g[v]) if(to.F!=p){
    par[to.F]=v;
    parCost[to.F]=to.S;
    dep[to.F]=dep[v]+1;
    dfs_cons(to.F, v);
  }
  info[v] = node(v, p);
}

ll dfs(int v, int p){
  vis[v]=true;
  ll base=0;
  int extra = g[v].size()-stat;

  for(auto to:lim[v]) if(to.F!=p){
    base+=dfs(to.F, v);
  }

  ll ex1=(v? (info[v].find_sum(max(extra-1, 0)) + parCost[v]) : 1000000000000000000);
  ll ex2=info[v].find_sum(extra);

  base+=min(ex1, ex2);
  ll add = max(0LL, ex1-ex2);

  if(v) info[p].update(v, add);
  return base;
}

vector<ll> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
  vector<ll> res(N, 0);
  n=N;
  forn(i, n-1){
    g[U[i]].PB({V[i], W[i]});
    g[V[i]].PB({U[i], W[i]});
    res[0]+=W[i];
  }

  dfs_cons(0, 0);
  forn(i, n) deg[g[i].size()].PB(i);

  forn(i, n-1){
    int u=U[i], v=V[i], w=W[i];
    int d = min(g[u].size(), g[v].size());
    ar[d].PB(MP(u, MP(v, w)));
  }

  dforsn(i, 1, n){
    stat=i;
    for(auto edge:ar[i+1]){
      lim[edge.F].PB(MP(edge.S.F, edge.S.S));
      lim[edge.S.F].PB(MP(edge.F, edge.S.S));
    }
    for(auto v:deg[i+1]) deps.insert(v);
    for(auto v:deps) if(!vis[v]) res[i]+=dfs(v, par[v]);
    for(auto v:deps) vis[v]=false;
  }
  return res;
}

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