이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |