제출 #564342

#제출 시각아이디문제언어결과실행 시간메모리
564342ngpin04다리 (APIO19_bridges)C++14
59 / 100
3059 ms15724 KiB
#include <bits/stdc++.h> #define fi first #define se second #define mp make_pair #define TASK "" #define bit(x) (1LL << (x)) #define getbit(x, i) (((x) >> (i)) & 1) #define ALL(x) (x).begin(), (x).end() using namespace std; template <typename T1, typename T2> bool mini(T1 &a, T2 b) { if (a > b) {a = b; return true;} return false; } template <typename T1, typename T2> bool maxi(T1 &a, T2 b) { if (a < b) {a = b; return true;} return false; } mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count()); int rand(int l, int r) { return l + rd() % (r - l + 1); } const int N = 1e5 + 5; const int K = 300; const int oo = 1e9; const long long ooo = 1e18; const int mod = 1e9 + 7; // 998244353; const long double pi = acos(-1); vector <int> a[2 * N]; int val[2 * N]; int *where[2 * N]; int tmpw[N]; int ind[N]; int ans[N]; int par[N]; int fr[N]; int to[N]; int op[N]; int w[N]; int s[N]; int d[N]; int n,m,q,timer; bool flag[N]; void rollback() { *where[timer] = val[timer]; timer--; } void change(int &a, int b) { timer++; where[timer] = &a; val[timer] = a; a = b; } int getpar(int u) { return (par[u] < 0) ? u : (getpar(par[u])); } void join(int u, int v) { u = getpar(u); v = getpar(v); if (u == v) return; if (par[u] > par[v]) swap(u, v); change(par[u], par[u] + par[v]); change(par[v], u); } void compress() { vector <int> val; for (int i = 1; i <= m; i++) val.push_back(w[i]); for (int i = 1; i <= q; i++) val.push_back(d[i]); sort(ALL(val)); for (int i = 1; i <= m; i++) w[i] = lower_bound(ALL(val), w[i]) - val.begin() + 1; for (int i = 1; i <= q; i++) d[i] = lower_bound(ALL(val), d[i]) - val.begin() + 1; } void solve(int l, int r) { timer = 0; for (int i = 1; i <= n; i++) par[i] = -1; for (int i = 1; i <= m; i++) flag[i] = false; vector <int> ed; vector <int> qr; for (int i = l; i <= r; i++) { if (op[i] == 1) { ed.push_back(s[i]); flag[s[i]] = true; } else qr.push_back(i); } sort(ALL(qr), [](int i, int j) { return d[i] > d[j]; }); { for (int i = 1; i <= m; i++) a[w[i]].push_back(i); int it = 0; for (int i = m + q; i >= 1; i--) { for (int j : a[i]) ind[++it] = j; a[i].clear(); } } int it = 1; for (int i : qr) { while (it <= m && w[ind[it]] >= d[i]) { if (!flag[ind[it]]) join(fr[ind[it]], to[ind[it]]); it++; } int cur = timer; for (int j = l; j <= i; j++) if (op[j] == 1) tmpw[s[j]] = d[j]; for (int j : ed) { int val = (tmpw[j] == 0) ? w[j] : tmpw[j]; if (val >= d[i]) join(fr[j], to[j]); } ans[i] = -par[getpar(s[i])]; for (int j : ed) tmpw[j] = 0; while (timer != cur) rollback(); } for (int i = l; i <= r; i++) if (op[i] == 1) w[s[i]] = d[i]; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); #ifdef ONLINE_JUDGE // freopen(TASK".inp","r",stdin); // freopen(TASK".out","w",stdout); #endif cin >> n >> m; for (int i = 1; i <= m; i++) cin >> fr[i] >> to[i] >> w[i]; cin >> q; for (int i = 1; i <= q; i++) cin >> op[i] >> s[i] >> d[i]; compress(); for (int l = 1; l <= q; l++) { int r = min(q, l + K); solve(l, r); l = r; } for (int i = 1; i <= q; i++) if (op[i] == 2) cout << ans[i] << "\n"; return 0; }
#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...