Submission #1063177

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063177		vjudge1	Road Closures (APIO21_roads)	C++17	100 / 100	127 ms	52680 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<ll,ll>;
using tii = tuple<int,int,int>;

const int nmax = 1e5 + 5;

int occ[nmax], flag;
struct Sons {
   multiset<pii> active, inactive;
   ll cost = 0;
   
   int required = 0;
   
   void insert(int T, int NT) {
      if(T == -1 && NT == -1) return;
      if(T <= NT) {
         cost += T;
         active.emplace(T - NT, NT);
      }
      else {
         inactive.emplace(T - NT, NT);
         cost += NT;
      }
   }
   
   void gerer() { // doar fa un treap in pula mea
      while(sz(active) < required && sz(inactive)) {
         auto [a, b] = *inactive.begin();
         inactive.erase(inactive.begin());
         cost += a;
         active.emplace(a, b);
      }
      while(sz(active) && active.rbegin() -> first > 0 && sz(active) > required) {
         auto [a, b] = *active.rbegin();
         cost -= a;
         active.erase(active.find(pii{a, b}));
         inactive.emplace(a, b);
      }
      while(sz(active) && sz(inactive) && active.rbegin() -> first > inactive.begin() -> first) {
         auto [a, b] = *active.rbegin();
         auto [c, d] = *inactive.begin();
         cost -= a;
         cost += c;
         active.erase(active.find(pii{a, b}));
         inactive.erase(inactive.find(pii{c, d}));
         active.emplace(c, d);
         inactive.emplace(a, b);
      }
   }
   void cut() {
      required++;
   }
   
   void erase(int T, int NT) {
      if(T == -1 && NT == -1) return;
      T -= NT;
      if(active.count(pii{T, NT})) {
         active.erase(active.find(pii{T, NT}));
         cost -= T, cost -= NT;
      }
      else {
         cost -= NT;
         inactive.erase(inactive.find(pii{T, NT}));
      }
      return;
   }
   
   pii query() {
      gerer();
      //if(flag == 3)
         //cerr << (sz(active)? active.rbegin() -> first : -1) << ' ' << (sz(inactive)? inactive.begin() -> first : -1) << '\n';
      if(required + 1 <= sz(active)) return pii{cost, cost};
      auto [a, b] = *inactive.begin();
      return pii{cost, cost + a};
   }
};


vector<pii> g[nmax];
vector<pii> t[nmax];
int N;

vector<int> incepe[nmax];

Sons inward[nmax];

pii dfs(int node, int f, int f_w) {
   occ[node] = flag;
   vector<pii> TNT;
   for(auto [a, w] : t[node]) {
      if(a == f) continue;
      auto [st, snt] = dfs(a, node, w);
      TNT.emplace_back(st, snt);
      inward[node].insert(st, snt);
   }
   
   auto [RT, RNT] = inward[node].query();
   for(auto [x, y] : TNT)
      inward[node].erase(x, y);
   
   
   //cerr << node << ": " << RT + f_w << ' ' << RNT << '\n';
   
   return pii{RT + f_w, RNT};
}

std::vector<long long> minimum_closure_costs(signed N_, std::vector<signed> U, std::vector<signed> V, std::vector<signed> W) {
   N = N_;
   ll sum = 0;
   for(int i = 0; i < sz(U); i++) {
      g[U[i]].emplace_back(V[i], W[i]);
      g[V[i]].emplace_back(U[i], W[i]);
      sum += W[i];
   }
   vector<ll> rez(N);
   rez[0] = sum;
   
   for(int i = 0; i < N; i++) {
      incepe[sz(g[i]) - 1].emplace_back(i);
   }
   
   vector<int> withme;
   for(int i = N - 1; i > 0; i--) {
      //cerr << "---------\n";
      for(auto x: incepe[i]) {
         for(auto [a, b] : g[x]) {
            if(sz(g[a]) < sz(g[x]))  inward[x].insert(b, 0);
            else {
               if(sz(g[a]) > sz(g[x]) || (sz(g[a]) == sz(g[x]) && a > x))
                  t[x].emplace_back(a, b),
                  t[a].emplace_back(x, b);
               if(sz(g[a]) > sz(g[x]))
                  inward[a].erase(b, 0);
            }
         }
         withme.emplace_back(x);
      }
      
      if(sz(withme) > 0)  {
         //for(auto x : withme) cerr << x << ' ';
         //cerr << "\n--\n";
      
         flag++;
         
         for(auto x : withme) {
            if(occ[x] != flag)
               rez[i] += dfs(x, x, 0).second;
         }
         
         for(auto x : withme)
            inward[x].cut();
      }
      //cerr << rez[i] << '\n';
   }
   return rez;
}

#undef int
//101308465+
//22623807+
//229740165

• 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