Submission #975213

#TimeUsernameProblemLanguageResultExecution timeMemory
975213oviyan_gandhiBridges (APIO19_bridges)C++17
0 / 100
3067 ms16328 KiB
#include <bits/stdc++.h> using namespace std; #define int long long typedef pair<int, int> pii; #define N 50001 #define M 100001 int lnk[N], sz[N]; void build(int n){ fill(sz, sz+n+1, 1); iota(lnk, lnk+n+1, 0); } int root(int x){ return lnk[x] == x ? x : (lnk[x] = root(lnk[x])); } void unite(int x, int y){ x = root(x), y = root(y); if (x == y) return; if (sz[x] < sz[y]) swap(x, y); sz[x] += sz[y]; lnk[y] = x; } struct Edge { int a, b, w, i; bool operator < (const Edge &o) const { return w > o.w; } }; Edge edges[M], sorted[M], queries[M]; vector<int> adj[N]; bool vis[N]; int ans[M]; int32_t main(){ // input ios_base::sync_with_stdio(false); cin.tie(NULL); int n, m; cin >> n >> m; for (int i = 1; i <= m; i++){ cin >> edges[i].a >> edges[i].b >> edges[i].w; edges[i].i = i; } int q; cin >> q; for (int i = 1; i <= q; i++){ cin >> queries[i].a >> queries[i].b >> queries[i].w; queries[i].i = i; } int bsz = ceil(sqrt(q)); for (int s = 1; s <= q; s += bsz){ build(n); vector<Edge> qu; map<int, int> changed; for (int i = s; i < min(q+1, s+bsz); i++){ if (queries[i].a == 1) changed[queries[i].b] = edges[queries[i].b].w; else qu.push_back(queries[i]); } sort(qu.begin(), qu.end()); for (int i = 1; i <= m; i++) sorted[i] = edges[i]; sort(sorted+1, sorted+m+1); int j = 1; for (auto [_, s, w, idx] : qu){ for (; j <= m && sorted[j].w >= w; j++) if (!changed.count(sorted[j].i)) unite(sorted[j].a, sorted[j].b); map<int, int> curr(changed); for (int i = s; i < idx; i++) if (queries[i].a == 1) curr[queries[i].b] = queries[i].w; for (auto [ei, ew] : curr){ if (ew >= w && root(edges[ei].a) != root(edges[ei].b)){ adj[root(edges[ei].a)].push_back(root(edges[ei].b)); adj[root(edges[ei].b)].push_back(root(edges[ei].a)); } } fill(vis, vis+n+1, false); queue<int> q; q.push(root(s)); vis[root(s)] = true; while (!q.empty()){ int u = q.front(); q.pop(); ans[idx] += sz[u]; for (int v : adj[u]){ if (!vis[v]){ vis[v] = true; q.push(v); } } } for (auto [ei, ew] : curr){ adj[root(edges[ei].a)].clear(); adj[root(edges[ei].b)].clear(); } } for (int i = s; i < min(q+1, s+bsz); i++) if (queries[i].a == 1) changed[queries[i].b] = queries[i].w; for (auto [i, w] : changed) edges[i].w = w; } for (int i = 1; i <= q; i++) if (ans[i]) 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...