Submission #934550

#TimeUsernameProblemLanguageResultExecution timeMemory
934550VladaMG98Bridges (APIO19_bridges)C++17
73 / 100
3033 ms9324 KiB
// Problem: B - Bridges // Contest: Virtual Judge - 2024-02-27 APIO Simulation // URL: https://vjudge.net/contest/612540#problem/B // Memory Limit: 512 MB // Time Limit: 3000 ms // // Powered by CP Editor (https://cpeditor.org) #include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for(int i = a; i < (b); ++i) #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() #define print(A,t) cerr << #A << ": "; copy(all(A),ostream_iterator<t>(cerr," " )); cerr << endl #define prArr(A,n,t) cerr << #A << ": "; copy(A,A + n,ostream_iterator<t>(cerr," " )); cerr << endl #define what_is(x) cerr << #x << " is " << x << endl typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef vector<int> vi; const int MAXN = 50010, MAXM = 100010, MAXQ = 100010; int N, M, Q; int from[MAXM], to[MAXM], weg[MAXM]; int type[MAXQ], a[MAXQ], b[MAXQ], ans[MAXQ]; struct event { int key, index; // index > 0 -- it is an edge index // index < 0 -- it is a query index event() {} event (int _key, int _index) : key(_key), index(_index) {} bool operator <(const event &other) const { if (key == other.key) return index < other.index; return key < other.key; } }; struct dsu_rollback { vi par, sz; stack<int> roll; dsu_rollback (int _n) { par.resize(_n + 1); sz.resize(_n + 1); for (int i = 1; i <= _n; i++) { par[i] = i; sz[i] = 1; } } int get (int x) { while (par[x] != x) x = par[x]; return x; } bool unite (int u, int v) { u = get(u); v = get(v); if (u == v) return false; if (sz[u] > sz[v]) swap(u, v); roll.push(u); par[u] = par[v]; sz[v] += sz[u]; return true; } void rollback (int wanted) { while (sz(roll) > wanted) { int k = roll.top(); roll.pop(); sz[par[k]] -= sz[k]; par[k] = k; } } int get_size (int u) { return sz[get(u)]; } }; bool in_current[MAXM]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); vector<event> ALL_EVENTS; cin >> N >> M; for (int i = 1; i <= M; i++) { cin >> from[i] >> to[i] >> weg[i]; } cin >> Q; for (int i = 1; i <= Q; i++) { cin >> type[i] >> a[i] >> b[i]; } const int B = 500; for (int i = 1; i <= Q; i += B) { int l = i, r = min(Q, l + B - 1); // we want to process all the queries between l and r set<int> current_vec; for (int j = l; j <= r; j++) { if (type[j] == 1) { current_vec.insert(a[j]); in_current[a[j]] = true; } } // gathering all previous edges vector<event> events; for (int j = 1; j <= M; j++) { if (!in_current[j]) { events.emplace_back(weg[j], j); } } // gathering all the queries for (int j = l; j <= r; j++) { if (type[j] == 2) { events.emplace_back(b[j], -j); } } // sorting everything together sort(all(events)); reverse(all(events)); dsu_rollback d(N); for (auto ev : events) { if (ev.index > 0) { d.unite(from[ev.index], to[ev.index]); } else { set<int> curr = current_vec; // it is a query, so create a small graph int prev_size = d.roll.size(); int query_index = -ev.index; for (int j = query_index - 1; j >= l; j--) { if (type[j] == 2) continue; if (curr.count(a[j])) { if (b[j] >= ev.key) { d.unite(from[a[j]], to[a[j]]); } curr.erase(a[j]); } } for (auto e : curr) { if (weg[e] >= ev.key) d.unite(from[e], to[e]); } ans[query_index] = d.get_size(a[query_index]); d.rollback(prev_size); } } for (int j = l; j <= r; j++) { if (type[j] == 1) { weg[a[j]] = b[j]; in_current[a[j]] = false; } } } for (int i = 1; i <= Q; i++) { if (type[i] == 2) { cout << ans[i] << endl; } } 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...