Submission #1074436

#TimeUsernameProblemLanguageResultExecution timeMemory
1074436khanhtbBridges (APIO19_bridges)C++17
0 / 100
1198 ms273524 KiB
#include <bits/stdc++.h> #define ll long long #define ull unsigned long long #define ld long double #define pb push_back #define pf push_front #define vi vector<int> #define vii vector<vi> #define pll pair<int, int> #define vpll vector<pint> #define all(a) a.begin(), a.end() #define fi first #define se second using namespace std; const int mod = 1e9+7; const ll inf = 2e18; const int B = 1008; const int N = 1e5 + 8; struct DSU_roll_back{ vector<int> par,sz; vector<pair<int &,int>> history; void init(int n){ par = vector<int> (n+5); sz = vector<int> (n+5,1); iota(all(par),0); } int fs(int v){ return par[v] == v?v:fs(par[v]); } void us(int u, int v){ u = fs(u), v = fs(v); if(u == v) return; if(sz[u] < sz[v]) swap(u,v); history.pb({sz[u],sz[u]}); history.pb({par[v],par[v]}); par[v] = u; sz[u] += sz[v]; } int now_time(){ return history.size(); } void roll_back(int time){ while(now_time() > time){ history.back().fi = history.back().se; history.pop_back(); } } int size(int u){ return sz[fs(u)]; } }; struct query{ int id,t,v,w; }; struct edge{ int u,v,w; }; vector<edge> ed = {{0,0,0}}; int n,m,q; vector<query> qr[N/B+2]; int ans[N]; bool mark[N]; int t[N]; void solve(){ cin >> n >> m; DSU_roll_back dsu; for(int i = 1; i <= m; i++){ int u,v,w;cin >> u >> v >> w; ed.pb({u,v,w}); } cin >> q; for(int i = 0; i < q; i++){ int v,w;cin >> t[i] >> v >> w; qr[i/B].pb({i,t[i],v,w}); } for(int block = 0; block <= (q-1)/B; block++){ dsu.init(n); vector<edge> unchange; for(auto [id,t,v,w]:qr[block]){ if(t == 1) mark[v] = 1; } sort(all(qr[block]),[&](query a, query b){ return a.w > b.w; }); for(int i = 1; i <= m; i++){ if(!mark[i]) unchange.pb(ed[i]); } sort(all(unchange),[&](edge a, edge b){ return a.w < b.w; }); for(int i = 0; i < qr[block].size(); i++){ auto [id,t,v,w] = qr[block][i]; while(unchange.back().w >= w){ dsu.us(unchange.back().u,unchange.back().v); unchange.pop_back(); } if(t == 2){ int time = dsu.now_time(); for(int j = 0; j < qr[block].size(); j++){ auto [id1,t1,v1,w1] = qr[block][j]; if(t1 == 1){ if(id1 < id && j < i) dsu.us(ed[v1].u,ed[v1].v); else if(id1 > id && ed[v1].w >= w) dsu.us(ed[v1].u,ed[v1].v); } } ans[id] = dsu.size(v); dsu.roll_back(time); } } for(auto [id,t,v,w]:qr[block]) if(t == 1) ed[v].w = w, mark[v] = 0; } for(int i = 0; i < q; i++){ if(t[i] == 2) cout << ans[i] << '\n'; } } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen("test.inp", "r")){ freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout); } int T = 1; // cin >> T; for (int i = 1; i <= T; i++){ solve(); cout << '\n'; } }

Compilation message (stderr)

bridges.cpp: In function 'void solve()':
bridges.cpp:92:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         for(int i = 0; i < qr[block].size(); i++){
      |                        ~~^~~~~~~~~~~~~~~~~~
bridges.cpp:100:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |                 for(int j = 0; j < qr[block].size(); j++){
      |                                ~~^~~~~~~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:122:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:123:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |         freopen("test.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...