#include <bits/stdc++.h> #define time() cerr << " \n " << "Time : " << 1000.0 * clock() / CLOCKS_PER_SEC << "ms." #define FOR(i, a, b) for (int i = a, _b = b; i <= _b; ++i) #define FORD(i, a, b) for (int i = a, _b = b; i >= _b; --i) #define all(x) x.begin(), x.end() #define uni(x) x.erase(unique(all(x)), x.end()) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define dbg(...) cerr << "[ " << #__VA_ARGS__ << " ] = ", debug(__VA_ARGS__) template<typename T> void debug(T x) { cerr << x << "\n\n"; } template<typename T, typename... Args> void debug(T x, Args... args) { cerr << x << " , ", debug(args...); } // -------------------------------------------------------------------------------------------------------------------- const int maxn = 1e5 + 3; int n, q, m; vector<array<int, 3>> g[maxn]; // -------------------------------------------------------------------------------------------------------------------- struct Qr { int op, a, b, id; } qrs[maxn]; // Khong lien thong, co canh trung vector<array<int, 3>> eds; namespace sub1 { bool vis[maxn]; void dfs(int u, int p, int cur_w) { vis[u] = true; for (auto tmp : g[u]) { int v = tmp[0], w = tmp[1]; if (v == p || w < cur_w || vis[v]) continue; dfs(v, u, cur_w); } } void solve() { FOR(iq, 1, q) { int op = qrs[iq].op; if (op & 1) { int pos = qrs[iq].a, val = qrs[iq].b; FOR(u, 1, n) { FOR(j, 0, (int)g[u].size() - 1) { int v = g[u][j][0], id = g[u][j][2]; if (id == pos) { g[u][j][1] = val; } } } } else { int S = qrs[iq].a, cur_w = qrs[iq].b; dfs(S, -1, cur_w); int res = 0; FOR(i, 1, n) res += vis[i]; cout << res << '\n'; FOR(i, 1, n) vis[i] = false; } } } } namespace sub3 { ll ans[maxn]; bool approve() { FOR(iq, 1, q) { if (qrs[iq].op == 1) return false; } return true; } bool cmpQ(const Qr &x, const Qr &y) { return x.b > y.b; } vector<array<int, 3>> eds; struct DSU { vector<int> e; void init() {e.assign(n + 3, -1);} int get(int u) {return e[u] < 0 ? u : e[u] = get(e[u]);} bool unite(int u, int v) { u = get(u); v = get(v); if (u == v) return false; if (e[u] > e[v]) swap(u, v); e[u] += e[v]; e[v] = u; return true; } }; bool cmpE(const array<int, 3> &x, const array<int, 3> &y) { return x[2] > y[2]; } void solve() { sort(qrs + 1, qrs + q + 1, cmpQ); DSU dsu; dsu.init(); FOR(u, 1, n) { for (auto tmp : g[u]) { eds.push_back({u, tmp[0], tmp[1]}); } } sort(all(eds), cmpE); int j = 0; FOR(iq, 1, q) { int S = qrs[iq].a, w = qrs[iq].b; while (j < (int)eds.size() && w <= eds[j][2]) { dsu.unite(eds[j][0], eds[j][1]); ++j; } ans[qrs[iq].id] = -dsu.e[dsu.get(S)]; } FOR(i, 1, q) { cout << ans[i] << '\n'; } } } namespace sub2 { bool approve() { if (m != n - 1) return false; FOR(i, 0, m - 1) { if (eds[i][0] != i + 1 || eds[i][1] != i + 2) return false; } return true; } int seg[maxn << 2]; void upd(int id, int l, int r, int pos, int val) { if (l == r) return void(seg[id] = val); int mid = l + r >> 1; if (pos <= mid) upd(id << 1, l, mid, pos, val); else upd(id << 1 | 1, mid + 1, r, pos, val); seg[id] = min(seg[id << 1], seg[id << 1 | 1]); } int get(int id, int l, int r, int u, int v) { if (l > v || r < u) return 1e9; if (l >= u && r <= v) return seg[id]; int mid = l + r >> 1; return min(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v)); } ll f[maxn]; void solve() { FOR(i, 0, m - 1) { f[eds[i][0]] = eds[i][2]; upd(1, 1, n - 1, eds[i][0], eds[i][2]); } FOR(iq, 1, q) { int op = qrs[iq].op; if (op & 1) { int pos = qrs[iq].a, val = qrs[iq].b; f[pos] = val; upd(1, 1, n - 1, pos, val); } else { int S = qrs[iq].a, cur_w = qrs[iq].b; int low = 1, high = S - 1; while (low <= high) { int mid = low + high >> 1; if (get(1, 1, n - 1, mid, S - 1) >= cur_w) high = mid - 1; else low = mid + 1; } int l = low; low = S, high = n - 1; while (low <= high) { int mid = low + high >> 1; if (get(1, 1, n - 1, S, mid) >= cur_w) low = mid + 1; else high = mid - 1; } int r = high + 1; cout << r - l + 1 << '\n'; } } } } void solve() { cin >> n >> m; FOR(i, 1, m) { int u, v, w; cin >> u >> v >> w; if (u > v) swap(u, v); g[u].push_back({v, w, i}); g[v].push_back({u, w, i}); eds.push_back({u, v, w}); } cin >> q; FOR(i, 1, q) { cin >> qrs[i].op >> qrs[i].a >> qrs[i].b; qrs[i].id = i; } if (sub2 :: approve()) return sub2 :: solve(), void(); if (sub3 :: approve()) return sub3 :: solve(), void(); sub1 :: solve(); } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define TASK "test" if (fopen(TASK".INP", "r")) { freopen(TASK".INP", "r", stdin); freopen(TASK".OUT", "w", stdout); } solve(); time(); return 0; }

bridges.cpp: In function 'int main()':
bridges.cpp:262:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  262 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:263:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  263 |         freopen(TASK".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~