Submission #966758

#	Time	Username	Problem	Language	Result	Execution time	Memory
966758		kilkuwu	Bridges (APIO19_bridges)	C++17	0 / 100	911 ms	67228 KiB

bridges

#include <bits/stdc++.h>

#define nl '\n'

#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace __gnu_pbds;

template <typename T>
using ordered_set = tree<T, null_type, std::less<T>, rb_tree_tag,
                         tree_order_statistics_node_update>;

struct DSU {
  std::vector<int> e;

  DSU(int n) : e(n, -1) {}

  int find(int u) {
    return e[u] < 0 ? u : e[u] = find(e[u]);
  }
  
  bool merge(int u, int v) {
    u = find(u), v = find(v);
    if (u == v) return false;
    if (e[u] > e[v]) std::swap(u, v);
    e[u] += e[v];
    e[v] = u;
    return true;
  } 

  bool same(int u, int v) {
    return find(u) == find(v);
  }
  
  int size(int u) {
    return -e[find(u)];
  }
};

template <typename T>
using PQG = std::priority_queue<T, std::vector<T>, std::greater<T>>;

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  
  int n, m;
  std::cin >> n >> m;
  
  std::vector<std::vector<int>> adj(n + 1);
  struct Edge {
    int u, v, d, i;

    inline int other(int x) { return u ^ v ^ x; }

    bool operator<(const Edge& rhs) {
      return d < rhs.d;
    }
  };

  std::vector<Edge> edges(m);
  std::vector<int> pa(n), ca(n);

  for (int i = 0; i < m; i++) {
    int u, v, d;
    std::cin >> u >> v >> d;
    adj[u].emplace_back(i);
    adj[v].emplace_back(i);
    edges[i] = {u, v, d, i};
    pa[v] = u;
    ca[v] = d;
  }

  if (n == 1) {
    int q;
    std::cin >> q;
    while (q--) {
      int t, a, b;
      std::cin >> t >> a >> b;
      if (t == 2) {
        std::cout << 1 << nl;
      }
    }
    return 0;
  }

  std::vector<ordered_set<std::pair<int, int>>> f(n + 1);

  auto delete_contribution = [&](int u) -> void {
    int path = ca[u];
    for (int v = u / 2; v > 0; v >>= 1) {
      f[v].erase({path, u});
      if (v != 1) {
        path = std::min(path, ca[v]);
      }
    }
  };

  auto add_contribution = [&](int u) -> void {
    int path = ca[u];
    for (int v = u / 2; v > 0; v >>= 1) {
      f[v].insert({path, u});
      if (v != 1) {
        path = std::min(path, ca[v]);
      }
    }
  };

  for (int i = 2; i <= n; i++) {
    add_contribution(i);
  }

  auto ask = [&](int u, int w) {
    while (u > 1 && ca[u] >= w) {
      u /= 2;
    }
    auto it = f[u].order_of_key({w, -1});
    return f[u].size() - it + 1;
  };

  int q;
  std::cin >> q;
  while (q--) {
    int t, a, b;
    std::cin >> t >> a >> b;
    if (t == 1) {
      --a;
      auto [u, v, d, i] = edges[a];
      delete_contribution(v);
      ca[v] = b;
      edges[a].d = b;
      add_contribution(v);
    } else {
      std::cout << ask(a, b) << nl;
    }
  }
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27