Submission #477082

#	Time	Username	Problem	Language	Result	Execution time	Memory
477082		Everifall	Road Closures (APIO21_roads)	C++14	100 / 100	555 ms	51688 KiB

roads

#include "roads.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef tree<pair<ll,int>,null_type,less<pair<ll,int> >,rb_tree_tag,tree_order_statistics_node_update> oset;
const int MAXN = 1e5 + 16;
const int INF = 1e9 + 16;
const ll INFLL = 1e16 + 16;
oset dpCost[MAXN];
vector<pair<int,ll> > adj[MAXN];
int ptrDp[MAXN],dep[MAXN],idxPar[MAXN];
ll costPar[MAXN],currBack[MAXN],currCost = 0;

void change(pair<ll,int> u,pair<ll,int> v,int id,int mn){
  if(u < *(dpCost[id].find_by_order(ptrDp[id]))){
    ptrDp[id]--;
    currCost -= u.first;
  }
  dpCost[id].erase(u);
  if(v < *(dpCost[id].find_by_order(ptrDp[id]))){
    ptrDp[id]++;
    currCost += v.first;
  }
  dpCost[id].insert(v);
  while(ptrDp[id] < max(0,mn)){
    currCost += dpCost[id].find_by_order(ptrDp[id]++)->first;
  }
  while(ptrDp[id] > max(0,mn) && dpCost[id].find_by_order(ptrDp[id]-1)->first > 0){
    currCost -= dpCost[id].find_by_order(--ptrDp[id])->first;
  }
  while(dpCost[id].find_by_order(ptrDp[id])->first < 0){
    currCost += dpCost[id].find_by_order(ptrDp[id]++)->first;
  }
}

void dfs(int u,int p){
  for(auto v : adj[u]){
    if(v.first != p){
      dep[v.first] = dep[u] + 1;
      dpCost[u].insert(make_pair(v.second,v.first));
      currBack[v.first] = v.second;
      ptrDp[u]++;
      dfs(v.first,u);
    }else{
      costPar[u] = v.second;
      idxPar[u] = v.first;
    }
  }
}

vector<ll> minimum_closure_costs(int N,vector<int> U,vector<int> V,vector<int> W){
  for(int i=0;i<N-1;i++){
    adj[U[i]].emplace_back(V[i],W[i]);
    adj[V[i]].emplace_back(U[i],W[i]);
    currCost += W[i];
  }
  adj[N].emplace_back(0,0);
  adj[0].emplace_back(N,0);
  for(int i=0;i<=N;i++){
    dpCost[i].insert(make_pair(INFLL,INF));
  }
  dfs(N,N);
  priority_queue<pair<int,int> > pq;
  for(int i=0;i<N;i++){
    pq.emplace(dep[i],i);
  }
  vector<ll> res;
  res.emplace_back(currCost);
  for(int i=1;i<N;i++){
    vector<pair<int,int> > proceed;
    while(!pq.empty()){
      auto curr = pq.top();
      int id = curr.second;
      pq.pop();
      if(adj[id].size() < i){
        continue;
      }
      proceed.emplace_back(curr);
      change(make_pair(INFLL,INF),make_pair(INFLL,INF),id,(int)adj[id].size()-i-1);
      ll temp = currCost + costPar[id];
      change(make_pair(INFLL,INF),make_pair(INFLL,INF),id,(int)adj[id].size()-i);
      temp -= currCost;
      change(make_pair(currBack[id],id),make_pair(temp,id),idxPar[id],(int)adj[idxPar[id]].size()-i);
      currBack[id] = temp;
    }
    res.emplace_back(currCost);
    for(auto u : proceed){
      pq.emplace(u);
    }
  }
  return res;
}

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:80:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   80 |       if(adj[id].size() < i){
      |          ~~~~~~~~~~~~~~~^~~

• 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