Submission #1063108

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063108		vjudge1	Road Closures (APIO21_roads)	C++17	0 / 100	2068 ms	46656 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;

struct Sons {
   multiset<pii> inside;
   ll cost = 0;
   
   int required = 0;
   
   void insert(int T, int NT) {
      if(T == -1 && NT == -1) return;
      inside.emplace(T - NT, NT);
   }
   
   void gerer() { // doar fa un treap in pula mea
      ;
   }
   void cut() {
      required++;
   }
   
   void erase(int T, int NT) {
      if(T == -1 && NT == -1) return;
      inside.erase(inside.find(pii{T - NT, NT}));
      return;
   }
   
   pii query() {
      ll sum = 0;
      for(auto [a, b] : inside) sum += b;
      auto it = inside.begin();
      int timer = 0;
      while(timer < required || (it != inside.end() && it -> first < 0)) timer++, sum  += it -> first, it = next(it);
      cost = sum;
      auto dual = cost;
      if(timer == required) dual += it -> first;
      return pii{cost, dual};
   }
};

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

vector<int> incepe[nmax];

Sons inward[nmax];
int occ[nmax], flag;

pii dfs(int node, int f, int f_w) {
   cerr << node << ' ' << f << '\t' << sz(inward[node].inside) << '\n';
   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);
   
   return pii{RT + f_w, RNT};
}

std::vector<long long> minimum_closure_costs(int N_, std::vector<int> U, std::vector<int> V, std::vector<int> 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--) {
      for(auto x: incepe[i]) {
         for(auto [a, b] : g[x]) {
            if(sz(g[a]) < sz(g[x]))  inward[x].insert(b, 0);
            else {
               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);
      }
      
      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;
}

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