| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 367791 | Jarif_Rahman | Bridges (APIO19_bridges) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const int SQ = 316;
struct dsu{
stack<tuple<int, int, int>> st;
int n;
int id[N];
stack<int> comp[N];
dsu(){
n = N;
for(int i = 0; i < n; i++) id[i] = i, comp[i].push(i);
}
int unite(int a, int b){
a = id[a], b = id[b];
if(a == b) return 0;
if(comp[a].size() > comp[b].size()) swap(a, b);
st.push({a, b, (int)comp[a].size()});
while(!comp[a].empty()){
int x = comp[a].top(); comp[a].pop();
id[x] = b;
comp[b].push(x);
}
return 1;
}
void rollback(){
auto [a, b, sz] = st.top(); st.pop();
while(sz--){
int x = comp[b].top(); comp[b].pop();
id[x] = a;
comp[a].push(x);
}
}
};
int sq;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m; cin >> n >> m;
tuple<ll, int, int> edge[m];
for(int i = 0; i < m; i++){
int a, b; ll w; cin >> a >> b >> w; a--, b--;
edge[i] = make_tuple(w, a, b);
}
int q; cin >> q;
tuple<ll, int, int> query[q];
for(int i = 0; i < q; i++){
int tt, s; ll w; cin >> tt >> s >> w; s--;
query[i] = {tt, s, w};
}
vector<int> ans;
dsu ds;
tuple<ll, int, int, int> calc[SQ+5];
bool ucng[m];
for(int i = 0; i < m; i++) ucng[i] = 1;
tuple<ll, int, int> edges[m];
for(int qi = 0; qi < q; qi+=SQ){
int ql = min(q-1, qi+SQ-1);
int cnt = 0;
for(int j = qi; j <= ql; j++){
auto [tt, s, w] = query[j];
if(tt == 1){
ucng[s] = 0;
}
else{
calc[cnt] = {w, s, cnt, j};
cnt++;
}
}
vector<int> anss(cnt);
int inx = 0;
for(int i = 0; i < m; i++){
if(ucng[i]) edges[inx++] = edge[i];
}
sort(edges, edges+inx);
sort(calc, calc+cnt, greater<tuple<ll, int, int, int>>());
int bc = inx-1;
for(int ii = 0; ii < cnt; ii++){
auto [w, s, in, jj] = calc[ii];
while(bc >= 0 && get<0>(edges[bc]) >= w){
auto [ww, a, b] = edges[bc]; bc--;
ds.unite(a, b);
}
int k = 0;
for(int j = jj-1; j >= qi; j--){
auto [tt, ss, ww] = query[j];
auto [www, a, b] = edge[ss];
if(tt == 2) continue;
if(ucng[ss]) continue;
if(ww >= w) k+=ds.unite(a, b);
ucng[ss] = 0;
}
for(int j = jj+1; j <= ql; j++){
auto [tt, ss, ww] = query[j];
auto [www, a, b] = edge[ss];
if(tt == 2) continue;
if(ucng[ss]) continue;
if(www >= w) k+=ds.unite(a, b);
}
for(int j = qi; j <= ql; j++){
auto [tt, ss, ww] = query[j];
if(tt == 1) ucng[ss] = 0;
}
anss[in] = ds.comp[ds.id[s]].size();
while(k--) ds.rollback();
}
for(int j = qi; j <= ql; j++){
auto [tt, ss, ww] = query[j];
if(tt == 1) ucng[ss] = 1;
}
ans.insert(ans.end(), anss.begin(), anss.end());
while(!ds.st.empty()) ds.rollback();
}
for(int x: ans) cout << x << "\n";
}