Submission #966746

#TimeUsernameProblemLanguageResultExecution timeMemory
966746kilkuwuBridges (APIO19_bridges)C++17
0 / 100
46 ms13580 KiB
#include <bits/stdc++.h> #define nl '\n' #ifdef LOCAL #include "template/debug.hpp" #else #define dbg(...) ; #define timer(...) ; #endif 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); 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); for (int i = 0; i < m; i++) { int u, v, d; std::cin >> u >> v >> d; --u, --v; adj[u].emplace_back(i); adj[v].emplace_back(i); edges[i] = {u, v, d, i}; } 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; } int bsize = std::sqrt(n) + 1; int bcnt = ((n - 2) / bsize) + 1; std::vector<PQG<std::pair<int, int>>> maxv(bcnt); for (int i = 0; i < m; i++) { int b = i / bsize; maxv[b].push({edges[i].d, i}); } auto count_left = [&](int u, int w) -> int { int b = (u - 1) / bsize; int lb = b * bsize; int ans = 0; for (int i = u - 1; i >= lb; i--) { if (edges[i].d < w) return ans; ans++; } // done all of it now int bb = b - 1; for (; bb >= 0; bb--) { if (maxv[bb].top().first < w) { break; } ans += bsize; } if (bb >= 0) { for (int j = (bb + 1) * bsize - 1; j >= bb * bsize; j--) { if (edges[j].d < w) return ans; ans++; } } dbg(u, w, ans); return ans; }; auto count_right = [&](int u, int w) -> int { if (u == n - 1) return 0; int b = u / bsize; int rb = std::min((b + 1) * bsize, m); dbg(u, rb); int ans = 0; for (int i = u; i < rb; i++) { if (edges[i].d < w) return ans; ans++; } // done all of it now int bb = b + 1; for (; bb < bcnt; bb++) { if (maxv[bb].top().first < w) { break; } int xx = bsize * bb; int yy = std::min((bsize + 1) * bb, m); ans += yy - xx; } if (bb < bcnt) { int rightb = std::min(m, (bb + 1) * bsize); for (int j = bb * bsize; j < rightb; j++) { if (edges[j].d < w) return ans; ans++; } } dbg(u, w, ans); return ans; }; int q; std::cin >> q; while (q--) { int t, a, b; std::cin >> t >> a >> b; --a; if (t == 1) { int id = a / bsize; edges[a].d = b; maxv[id].push({edges[a].d, a}); while (maxv[id].size()) { auto [x, y] = maxv[id].top(); if (edges[y].d != x) { maxv[id].pop(); } else { break; } } dbg(id, maxv[id].top(), maxv[id]); } else { std::cout << count_left(a, b) + count_right(a, b) + 1 << nl; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...