| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 370615 | 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 N = 5e4, M = 1e5, Q = 1e5, SQ = 316, lim = 2e5;
vector<int> sorter[lim];
tuple<int, int, int> srt[lim];
void counting_sort(tuple<int, int, int> *a, tuple<int, int, int> *b){
int mx = 0;
for(int i = 0; a+i < b; i++){
sorter[get<0>(*(a+i))].pb(i);
mx = max(mx, *(a+i));
}
int inx = 0;
for(int i = 0; i <= mx; i++){
while(!sorter[i].empty()) srt[inx++] = *(a+sorter[i].back())), sorter[i].pop_back();
}
for(int i = 0; i < inx; i++) *(a+i) = srt[i];
}
struct dsu{
int n;
vector<int> sz, p;
stack<tuple<int, int, int>> st;
dsu(int nn){
n = nn;
sz.resize(n, 1);
p.resize(n);
for(int i = 0; i < n; i++) p[i] = i;
}
int get(int x){
if(p[x] != x) return get(p[x]);
return p[x];
}
int unite(int a, int b){
a = get(a), b = get(b);
if(a == b) return 0;
if(sz[b] > sz[a]) swap(a, b);
st.push({a, b, sz[b]});
sz[a]+=sz[b];
sz[b] = 0;
p[b] = a;
return 1;
}
void rollback(){
auto [a, b, ss] = st.top(); st.pop();
sz[a]-=ss;
sz[b] = ss;
p[b] = b;
}
};
tuple<int, int, int> edge[M];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
vector<int> compressor;
map<int, int> mp;
int n, m; cin >> n >> m;
for(int i = 0; i < m; i++){
int a, b, w; cin >> a >> b >> w; a--, b--;
edge[i] = make_tuple(w, a, b);
compressor.pb(w);
}
int cmpr = 0;
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};
compressor.pb(w);
}
sort(compressor.begin(), compressor.end());
for(int i = 0; i < compressor.size(); i++){
if(i != 0 && compressor[i] == compressor[i-1]) continue;
mp[compressor[i]] = cmpr++;
}
for(int i = 0; i < m; i++) get<0>(edge[i]) = mp[get<0>(edge[i])];
for(int i = 0; i < q; i++) get<2>(query[i]) = mp[get<2>(query[i])];
vector<int> ans;
dsu ds(N);
vector<tuple<int, int, int>> calc;
bool ucng[M];
for(int i = 0; i < m; i++) ucng[i] = 1;
tuple<int, int, int> edges[M];
vector<int> cng;
for(int ql = 0; ql < q; ql+=SQ){
int qr = min(q-1, ql+SQ-1);
int cnt = 0;
for(int j = ql; j <= qr; j++){
auto [tt, s, w] = query[j];
if(tt == 1){
ucng[s] = 0;
}
else{
cnt++;
calc.pb({w, s, cnt-1});
}
}
int inx = 0;
for(int i = 0; i < m; i++){
if(ucng[i]) edges[inx++] = edge[i];
else cng.pb(i);
}
vector<int> anss(cnt);
vector<vector<pair<int, int>>> upd(cnt);
cnt = 0;
for(int j = ql; j <= qr; j++){
auto [tt, s, w] = query[j];
if(tt == 1){
get<0>(edge[s]) = w;
}
else{
for(int x: cng){
auto [ww, a, b] = edge[x];
if(ww >= w) upd[cnt].pb({a, b});
}
cnt++;
}
}
counting_sort(edges, edges+inx);
sort(calc.rbegin(), calc.rend());
int bc = inx-1;
for(auto [w, s, in]: calc){
while(bc >= 0 && get<0>(edges[bc]) >= w){
auto [ww, a, b] = edges[bc]; bc--;
ds.unite(a, b);
}
int k = 0;
for(auto [a, b]: upd[in]) k+=ds.unite(a, b);
anss[in] = ds.sz[ds.get(s)];
while(k--) ds.rollback();
}
ans.insert(ans.end(), anss.begin(), anss.end());
calc.clear();
for(int i = 0; i < m; i++) ucng[i] = 1;
cng.clear();
while(!ds.st.empty()) ds.rollback();
}
for(int x: ans) cout << x << "\n";
}