Submission #924013

#TimeUsernameProblemLanguageResultExecution timeMemory
924013ArpBridges (APIO19_bridges)C++17
0 / 100
1213 ms6480 KiB
#include<bits/stdc++.h> using namespace std; const int B = 1000; const int M = 1e5; int sz[M + 1]; int par[M + 1]; stack<int> st; void init(){ for(int i = 1; i <= M;i++){ sz[i] = 1; par[i] = i; } } int find(int a){ if(par[a] == a){ return a; } return par[a] = find(par[a]); } void join(int a,int b){ a = find(a); b = find(b); if(a == b) return; if(sz[a] > sz[b]) swap(a,b); sz[b] += sz[a]; par[a] = b; st.push(a); } void rollback(int s){ while((int) st.size() > s){ int a = st.top(); st.pop(); int p = find(a); sz[p] -= sz[a]; par[a] = a; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n,m; cin >> n >> m; vector<array<int,3>> bridge(m + 1); for(int i = 1;i <= m;i++){ cin >> bridge[i][0] >> bridge[i][1] >> bridge[i][2]; } int q; cin >> q; vector<array<int,3>> query(q); for(int i = 0;i < q;i++){ cin >> query[i][0] >> query[i][2] >> query[i][1]; } vector<int> ans(q); for(int i = 0;i < q;i += B){ init(); int l = i; int r = min(q - 1,i + B); vector<bool> isc(m + 1,false); vector<int> upd,ask; vector<vector<int>> tj(r - l + 1); for(int j = l;j <= r;j ++){ if(query[j][0] == 1) upd.push_back(query[j][1]); } for(int j = l;j <= r;j ++){ if(query[j][0] == 1){ isc[query[j][1]] = true; bridge[query[j][1]][2] = query[j][2]; }else{ for(int k : upd){ if(bridge[k][2] >= query[j][1]) tj[j - l].push_back(k); } ask.push_back(j); } } vector<int> uc; for(int j = 1;j <= m;j++){ if(!isc[j]){ uc.push_back(j); } } sort(uc.begin(),uc.end(),[&](int &a,int &b){ return bridge[a][2] > bridge[b][2]; }); sort(ask.begin(),ask.end(),[&](int &a,int &b){ return query[a][1] > query[b][1]; }); int cur = 0; for(int k : ask){ int w = query[k][1]; while(cur < (int) uc.size() && bridge[uc[cur]][2] >= w){ join(bridge[uc[cur]][0],bridge[uc[cur]][1]); ++ cur; } for(int e : tj[k - l]){ join(bridge[e][0],bridge[e][1]); } int my = query[k][2]; ans[k] = sz[find(my)]; rollback(cur); } } for(int i = 0;i < q;i++){ if(query[i][0] == 2) 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...