제출 #410667

#제출 시각아이디문제언어결과실행 시간메모리
410667dynam1c다리 (APIO19_bridges)C++17
13 / 100
3097 ms8964 KiB
//#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("Ofast") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #include <bits/stdc++.h> using namespace std; typedef long long ll; #define endl "\n" #define all(c) (c).begin(),(c).end() // when you ponder, divide and conquer struct DSU { int n; vector<int> link, sz; DSU(int n) : n(n), link(n), sz(n, 1) { iota(all(link), 0); } void reset() { iota(all(link), 0); sz.assign(n, 1); } void unite(int u, int v) { u = find(u), v = find(v); if (u == v) return; if (sz[u] < sz[v]) swap(u, v); sz[u] += sz[v]; link[v] = u; } int find(int v) { return link[v] == v ? v : link[v] = find(link[v]); } }; signed main() { // freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); std::ios::sync_with_stdio(false); cin.tie(0); int n, m, q; cin >> n >> m; vector<pair<int, int>> es(m); vector<int> ws(m); set<pair<int, int>> s; for (int i = 0; i < m; i++) { int x, y, w; cin >> x >> y >> w; x--, y--; s.emplace(-w, i); es[i] = {x, y}; ws[i] = w; } cin >> q; for (int qq = 0; qq < q; qq++) { int t, x, y; cin >> t >> x >> y; x--; if (t == 1) { s.erase({-ws[x], x}); ws[x] = y; s.insert({-ws[x], x}); } else { DSU dsu(n); for (auto [w, i] : s) if (-w < y) break; else dsu.unite(es[i].first, es[i].second); cout << dsu.sz[dsu.find(x)] << endl; } } } /* --- PSolving --- * Simplifying (getting rid of variables, conditions, code logic, etc.) * Reframing * Solving a subtask (subgoal, aux. problem, removing a condition or fixing a parameter, etc.) * Inducing * Divide and conquer * Working backwards * Visual intuition * !! Reductions don't have to be specializations, they can be generalizations */
#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...