| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1070658 | Tozzyyyy | 다리 (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.
#pragma GCC optimize("Ofast","unroll-loops")
#pragma GCC target("arch=skylake")
#include<bits/stdc++.h>
#define all(x) (x).begin() , (x).end()
#define pll pair<long long, long long>
#define pii pair<int , int>
#define fi first
#define se second
#define bit(i,j) ((j >> i) & 1)
using namespace std;
const long long inf = 1e18;
const int MAXN = 1e6+100;
const int mod = 1e9+7;
struct edge{
int u , v , w;
};
struct query{
int type , a , b;
};
int ans[MAXN] , par[MAXN] , sz[MAXN];
vector<pair<int & , int>> his;
int find(int x) { return x == par[x] ? x : find(par[x]); }
void join(int a , int b){
a = find(a) ;
b = find(b);
if(a == b) return ;
if(sz[a] < sz[b]) swap(a , b);
his.push_back({sz[a] , sz[a]});
his.push_back({par[b] , par[b]});
par[b] = a;
sz[a] += sz[b];
}
void roll_back(int until){
while(his.size() > until){
his.back().first = his.back().second;
his.pop_back();
}
}
int32_t main(){
//freopen("B.inp", "r", stdin);
//freopen("B.out", "w", stdout);
ios_base::sync_with_stdio(0); cin.tie(0);
int n , m; cin >> n >> m;
vector<edge> E(m + 1);
for(int i = 1 ; i <= m ; i++){
int x , y , w; cin >> x >> y >> w;
E[i] = {x , y , w};
}
int q; cin >> q;
vector<query> Q(q+1);
const int block = 200;
for(int i = 1 ; i <= q ; i++){
cin >> Q[i].type >> Q[i].a >> Q[i].b;
}
for(int bl = 1 ; bl <= q / block + (q % block != 0) ; bl++){
vector<int> b(m + 1) , un_change , change, g;
vector<query> ask;
his.clear();
for(int i = 1 ; i <= n ; i++) sz[i] = 1 , par[i] = i;
for(int i = (bl - 1) * block + 1 ; i <= min(bl * block , q) ; i++){
if(Q[i].type == 1) b[Q[i].a] = -1 , change.push_back(i);
else{
ask.push_back({i , Q[i].b , Q[i].a});
}
}
for(int i = 1 ; i <= m ; i++){
if(b[i] == 0) un_change.push_back(i);
else g.push_back(i);
}
sort(all(ask) , [&](query x , query y){
return x.a > y.a;
});
sort(all(un_change) , [&](int x , int y){
return E[x].w > E[y].w;
});
int j = 0;
for(int i = 0 ; i < ask.size() ; i++){
while(j < un_change.size() && E[un_change[j]].w >= ask[i].a){
join(E[un_change[j]].u , E[un_change[j]].v); j++;
}
int cnt = his.size();
for(int k = 0; k < change.size() ; k++){
if(change[k] < ask[i].type){
b[Q[change[k]].a] = Q[change[k]].b;
}
}
for(int k = 0; k < g.size() ; k++){
int id = g[k];
if(b[id] == -1){
if(E[id].w >= ask[i].a) join(E[id].u , E[id].v);
}else{
if(b[id] >= ask[i].a) join(E[id].u , E[id].v);
b[id] = -1;
}
}
ans[ask[i].type] = sz[find(ask[i].b)];
roll_back(cnt);
}
for(int k = 0; k < change.size() ; k++){
b[Q[change[k]].a] = Q[change[k]].b;
}
for(int i = 1 ; i <= m ; i++) if(b[i] != 0) E[i].w = b[i];
}
for(int i = 1 ; i <= q ; i++){
if(Q[i].type == 2) cout << ans[i] << "\n";
}
return 0;
}