Submission #727072

#TimeUsernameProblemLanguageResultExecution timeMemory
727072SanguineChameleonBridges (APIO19_bridges)C++17
13 / 100
3058 ms16792 KiB
#include <bits/stdc++.h> using namespace std; void just_do_it(); int main() { #ifdef KAMIRULEZ freopen("kamirulez.inp", "r", stdin); freopen("kamirulez.out", "w", stdout); #endif ios_base::sync_with_stdio(0); cin.tie(0); just_do_it(); return 0; } struct edge { int u, v, w; }; struct query { int t, x, y; }; const int maxN = 1e5 + 20; const int block = 1; vector<pair<int, int>> adj[maxN]; edge E[maxN]; query Q[maxN]; bool imp_edge[maxN]; bool imp_node[maxN]; int depth[maxN]; int par[maxN]; int sz[maxN]; vector<int> comp[maxN]; vector<pair<int, int>> vals[maxN]; int flag_comp[maxN]; int flag_imp[maxN]; int root(int u) { if (!par[u]) { return u; } return root(par[u]); } void update(int u, int v) { int ru = root(u); int rv = root(v); if (ru == rv) { return; } if (depth[ru] > depth[rv]) { swap(ru, rv); } par[ru] = rv; sz[rv] += sz[ru]; if (comp[ru].size() > comp[rv].size()) { swap(comp[ru], comp[rv]); } comp[rv].insert(comp[rv].end(), comp[ru].begin(), comp[ru].end()); if (depth[ru] == depth[rv]) { depth[rv]++; } } int res; void dfs(int u, int w, int query_id) { //cout << "dfs" << " " << u << '\n'; if (flag_imp[u] == query_id) { return; } flag_imp[u] = query_id; int ru = root(u); if (flag_comp[ru] != query_id) { res += sz[ru]; flag_comp[ru] = query_id; for (auto v: comp[ru]) { dfs(v, w, query_id); } } for (auto e: adj[u]) { int v = e.first; int edge_id = e.second; int cur = (lower_bound(vals[edge_id].begin(), vals[edge_id].end(), make_pair(query_id, -1)) - 1)->second; if (w <= cur) { dfs(v, w, query_id); } } } void just_do_it() { int n, m; cin >> n >> m; for (int i = 1; i <= m; i++) { cin >> E[i].u >> E[i].v >> E[i].w; } int q; cin >> q; for (int i = 0; i < q; i++) { cin >> Q[i].t >> Q[i].x >> Q[i].y; } for (int i = 1; i <= n; i++) { flag_comp[i] = -1; flag_imp[i] = -1; } for (int block_id = 0; block_id <= (q - 1) / block; block_id++) { int lt = block_id * block; int rt = min((block_id + 1) * block - 1, q - 1); for (int i = 1; i <= n; i++) { adj[i].clear(); imp_node[i] = false; } for (int i = 1; i <= m; i++) { imp_edge[i] = false; } vector<pair<int, int>> events; for (int i = lt; i <= rt; i++) { if (Q[i].t == 1) { imp_edge[Q[i].x] = true; } else { events.push_back({Q[i].y, -i}); } } for (int i = 1; i <= m; i++) { if (imp_edge[i]) { vals[i].clear(); vals[i].push_back({lt - 1, E[i].w}); int u = E[i].u; int v = E[i].v; imp_node[u] = true; imp_node[v] = true; adj[u].push_back({v, i}); adj[v].push_back({u, i}); } else { events.push_back({E[i].w, i}); } } for (int i = lt; i <= rt; i++) { if (Q[i].t == 1) { vals[Q[i].x].push_back({i, Q[i].y}); E[Q[i].x].w = Q[i].y; } } for (int i = 1; i <= n; i++) { depth[i] = 0; par[i] = 0; sz[i] = 1; comp[i].clear(); if (imp_node[i]) { comp[i].push_back(i); } } sort(events.begin(), events.end(), greater<pair<int, int>>()); for (auto e: events) { int id = e.second; if (id > 0) { int u = E[id].u; int v = E[id].v; //cout << "add" << " " << u << " " << v << " " << w << '\n'; update(u, v); } else { id = -id; int u = Q[id].x; int w = Q[id].y; //cout << "query" << " " << u << " " << w << '\n'; res = 0; dfs(u, w, id); cout << res << '\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...