Submission #1221570

#TimeUsernameProblemLanguageResultExecution timeMemory
1221570hoa208Bridges (APIO19_bridges)C++20
100 / 100
2833 ms9784 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++) #define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--) #define pa pair<ll, ll> #define fi first #define se second #define bit(mask, j) ((mask >> j) & 1) #define t_test int t;cin >> t;while(t--) const ll mod = 1e9 + 7; const ll INF = 1e18; inline void adm(ll &x){if(x>=mod)x%=mod;else if(x<0)x+=mod;} //-------------------------------------------------------------------- const ll BLOCK = 350; const ll N = 5e4 + 10; const ll M = 1e5 + 10; ll n, m; struct EDGE { ll u, v, d; }; struct EDGE2 { ll u, v, d, id; bool operator < (const EDGE2 & a) const { return d > a.d || (a.d == d && id < a.id); } }; EDGE ed[M]; vector<ll> edge; ll dx[M]; pa a[BLOCK + 10]; ll p[N], sz[N]; ll b[BLOCK + 10], res[BLOCK + 10]; ll findset(ll u) { if(p[u] == u) return u; return findset(p[u]); } void rollback() { ll v = edge.back(); edge.pop_back(); sz[p[v]] -= sz[v]; p[v] = v; } void ghep(ll u, ll v) { u = findset(u); v = findset(v); if(v == u) return; if(sz[v] > sz[u]) swap(u, v); edge.push_back(v); p[v] = u; sz[u] += sz[v]; } void hbmt() { cin >> n >> m; FOR(i, 1, m) { ll u, v, d; cin >> u >> v >> d; ed[i] = {u, v, d}; } ll q, dem = 0; cin >> q; vector<EDGE> vt, vr[BLOCK + 10]; vector<ll> q1; vector<EDGE2> ve; FOR(i, 1, n) p[i] = i, sz[i] = 1; FOR(i, 1, q) { ll x, u, v; cin >> x >> u >> v; if(x == 2) { vt.push_back({++dem, u, v}); } else { vt.push_back({-1, u, v}); q1.push_back(u); } if(i % BLOCK == 0 || i == q) { for(auto e : vt) { if(e.u != -1) { for(auto id : q1) { vr[e.u].push_back(ed[id]); } ve.push_back({e.v, 0, e.d, e.u}); } else { ed[e.v].d = e.d; dx[e.v] = 1; } } FOR(i, 1, m) { if(dx[i]) { dx[i] = 0; continue; } ve.push_back({ed[i].u, ed[i].v, ed[i].d, -1}); } sort(ve.begin(), ve.end()); for(auto e : ve) { ll u = e.u, v = e.v, w = e.d, id = e.id; if(id == -1) ghep(u, v); else { ll szz = edge.size(); for(auto f : vr[id]) { if(f.d >= w) ghep(f.u, f.v); } res[id] = sz[findset(u)]; while(edge.size() > szz) rollback(); } } while(edge.size() > 0) rollback(); FOR(i, 1, dem) { vr[i].clear(); cout << res[i] << '\n'; } vt.clear(); ve.clear(); q1.clear(); dem = 0; } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); if(fopen("hbmt.inp", "r")) { freopen("hbmt.inp", "r", stdin); freopen("hbmt.out", "w", stdout); } // t_test hbmt(); return 0; }

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:129:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |         freopen("hbmt.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:130:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |         freopen("hbmt.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...