제출 #559001

#제출 시각아이디문제언어결과실행 시간메모리
559001hollwo_pelw다리 (APIO19_bridges)C++17
100 / 100
2449 ms209352 KiB
#include <bits/stdc++.h> // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/trie_policy.hpp> // #include <ext/rope> using namespace std; // using namespace __gnu_cxx; // using namespace __gnu_pbds; void Hollwo_Pelw(); signed main(){ #ifndef hollwo_pelw_local if (fopen("A.inp", "r")) assert(freopen("A.inp", "r", stdin)), assert(freopen("A.out", "w", stdout)); #else auto start = chrono::steady_clock::now(); #endif cin.tie(0), cout.tie(0) -> sync_with_stdio(0); int testcases = 1; // cin >> testcases; for (int test = 1; test <= testcases; test++){ // cout << "Case #" << test << ": "; Hollwo_Pelw(); } #ifdef hollwo_pelw_local auto end = chrono::steady_clock::now(); cout << "\nExcution time : " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl; #endif } const int N = 5e4 + 5, M = 1e5 + 5, B = 1200; int n, m, q, u[M], v[M], w[M], t[M], x[M], y[M]; int change[M], par[N], siz[N], res[M]; vector<pair<int*, int>> st; vector<int> to_upd[M]; inline int find(int u) { return par[u] == u ? u : find(par[u]); } inline void merge(int u, int v) { if ((u = find(u)) != (v = find(v))) { if (siz[u] > siz[v]) swap(u, v); st.emplace_back(par + u, par[u]); st.emplace_back(siz + v, siz[v]); siz[par[u] = v] += siz[u]; } } inline void rollback(int k) { for (; (int) st.size() > k; st.pop_back()) *st.back().first = st.back().second; } void Hollwo_Pelw(){ cin >> n >> m; for (int i = 1; i <= m; i++) { cin >> u[i] >> v[i] >> w[i]; } cin >> q; for (int i = 1; i <= q; i++) { cin >> t[i] >> x[i] >> y[i]; } iota(par + 1, par + n + 1, 1); fill(siz + 1, siz + n + 1, 1); for (int l = 1, r = min(B, q); l <= q; l += B, r = min(r + B, q)) { vector<int> ask, upd, lef; fill(change + 1, change + m + 1, 0); for (int i = l; i <= r; i++) { if (t[i] == 1) { change[x[i]] = 1; upd.push_back(i); } else { ask.push_back(i); } } for (int i = 1; i <= m; i++) { if (!change[i]) lef.push_back(i); } for (int i = l; i <= r; i++) { if (t[i] == 1) { w[x[i]] = y[i]; } else { for (int j : upd) { if (w[x[j]] >= y[i]) to_upd[i].push_back(x[j]); } } } sort(ask.begin(), ask.end(), [&](const int &i, const int &j){ return y[i] > y[j]; }); sort(lef.begin(), lef.end(), [&](const int &i, const int &j){ return w[i] > w[j]; }); for (int i = 0, j = 0; i < (int) ask.size(); i++) { while (j < (int) lef.size() && w[lef[j]] >= y[ask[i]]) { merge(u[lef[j]], v[lef[j]]), j ++; } int k = st.size(); for (int z : to_upd[ask[i]]) { merge(u[z], v[z]); } res[ask[i]] = siz[find(x[ask[i]])]; rollback(k); } rollback(0); } for (int i = 1; i <= q; i++) if (t[i] == 2) cout << res[i] << '\n'; }
#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...