Submission #984904

#TimeUsernameProblemLanguageResultExecution timeMemory
984904TsaganaBridges (APIO19_bridges)C++14
100 / 100
1544 ms33448 KiB
#include<bits/stdc++.h> #define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie(); #define all(x) x.begin(), x.end() #define pii pair<int, int> #define pip pair<int, pii> #define int long long #define pq priority_queue #define lb lower_bound #define ub upper_bound #define pb push_back #define eb emplace_back #define F first #define S second using namespace std; struct Graph { int n, m, q; int sz[50005]; int dsu[50005]; int ans[100005]; int part = 1000; bool change[100005]; vector<pip> edg; vector<pii> ord; vector<pip> query; vector<pii> bridge[1005]; int find(int x) {return (dsu[x] == x ? x : find(dsu[x]));} void prepare() { for (int i = 1; i <= n; i++) {dsu[i] = i; sz[i] = 1;} for (int i = 0; i < m; i++) {change[i] = 0;} ord.clear(); } void join(int a, int b) { int pa = find(a), pb = find(b); if (pa == pb) return; if (sz[pa] < sz[pb]) swap(pa, pb); ord.pb({pa, pb}); dsu[pb] = pa; sz[pa] += sz[pb]; } void undo(int szz) { while (ord.size() > szz) { int pa = ord.back().F, pb = ord.back().S; ord.pop_back(); sz[pa] -= sz[pb]; dsu[pb] = pb; } } void update(int st) { int en = min(st + part, q); prepare(); vector<pip> qu, ed; vector<int> one; for (int i = st; i < en; i++) { if (query[i].F == 1) {change[query[i].S.F] = 1; one.pb(i);} else qu.pb({query[i].S.S, {query[i].S.F, i}}); } for (int i = 0; i < m; i++) if (!change[i]) ed.pb(edg[i]); for (int i = st; i < en; i++) { if (query[i].F == 1) edg[query[i].S.F].F = query[i].S.S; else { bridge[i-st].clear(); for (int q: one) if (edg[query[q].S.F].F >= query[i].S.S) bridge[i-st].pb(edg[query[q].S.F].S); } } sort(all(qu)); sort(all(ed)); int e = ed.size()-1; for (int i = qu.size()-1; i >= 0; i--) { int w = qu[i].F; int land = qu[i].S.F; int idx = qu[i].S.S; while (e >= 0 && ed[e].F >= w) {join(ed[e].S.F, ed[e].S.S); e--;} int szz = ord.size(); for (pii p: bridge[idx-st]) join(p.F, p.S); ans[idx] = sz[find(land)]; undo(szz); } } void solve() { cin >> n >> m; for (int i = 0; i < m; i++) {int u, v, w; cin >> u >> v >> w; edg.pb({w, {u, v}});} cin >> q; for (int i = 0; i < q; i++) { int t, x, y; cin >> t >> x >> y; if (t == 1) x--; query.pb({t, {x, y}}); } for (int st = 0; st < q; st += part) update(st); for (int i = 0; i < q; i++) if (query[i].F == 2) cout << ans[i] << '\n'; } } G; signed main(){IOS G.solve(); return 0;}

Compilation message (stderr)

bridges.cpp: In member function 'void Graph::undo(long long int)':
bridges.cpp:43:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   43 |   while (ord.size() > szz) {
      |          ~~~~~~~~~~~^~~~~
#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...