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 target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 1e5 + 9;
const ll mod = 1e9 + 7;
const ll B = 1e3;
struct Edge{
ll u,v,w;
};
Edge a[N];
struct Query{
ll type,x,y;
};
Query q[N];
ll n,m,ans[N],lab[N],Q;
vector<ll> change,unchange;
bool Is_change[N];
stack<LL> st;
bool lf(ll x,ll y){
return a[x].w > a[y].w;
}
ll Find(ll u){
if (lab[u] < 0) return u;
return Find(lab[u]);
}
void Union(ll P,ll Q){
ll r = Find(P),s = Find(Q);
if (r == s) return;
if (lab[r] > lab[s]) swap(r,s);
st.push({r,lab[r]}); st.push({s,lab[s]});
lab[r] += lab[s]; lab[s] = r;
}
void rollback(ll now){
while(st.size() > now){
lab[st.top().fs] = st.top().sc;
st.pop();
}
}
vector<ll> type2;
bool cmp(ll a,ll b){
return q[a].y > q[b].y;
}
void oper(ll L,ll R){
memset(Is_change,0,sizeof(Is_change)); memset(lab,-1,sizeof(lab));
change.clear(); unchange.clear();
for (ll i = L;i <= R;i++){
if (q[i].type == 1) Is_change[q[i].x] = 1,change.push_back(i);
else type2.push_back(i);
}
for (ll i = 1;i <= m;i++){
if (!Is_change[i]) unchange.push_back(i);
}
sort(unchange.begin(),unchange.end(),lf); sort(type2.begin(),type2.end(),cmp);
ll cur = 0;
for (auto i : type2){
ll wei = q[i].y,pos = q[i].x;
while(cur < unchange.size()){
Edge p = a[unchange[cur]];
if (p.w < wei) break;
ll u = p.u,v = p.v;
Union(u,v); cur++;
}
ll start = st.size(); //cout<<Find(2); exit(0);
for (auto j : change){
ll u = a[q[j].x].u,v = a[q[j].x].v,w = a[q[j].x].w;
//cout<<w; exit(0);
if (j > i){
if (w >= wei) Union(u,v);
}
else{
if (q[j].y >= wei) Union(u,v);
}
}
ll root = Find(pos); ans[i] = -lab[root];
//cout<<root<<" "<<ans[i]; exit(0);
rollback(start);
}
//exit(0);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#define task "tst"
if (fopen(task".INP","r")){
freopen(task".INP","r",stdin);
//freopen(task".OUT","w",stdout);
}
cin>>n>>m;
for (ll i = 1;i <= m;i++) cin>>a[i].u>>a[i].v>>a[i].w;
cin>>Q;
for (ll i = 1;i <= Q;i++) cin>>q[i].type>>q[i].x>>q[i].y;
for (ll i = 1;i <= Q;i += B) oper(i,min(Q,i + B - 1));
for (ll i = 1;i <= Q;i++) if (ans[i]) cout<<ans[i]<<"\n";
}
Compilation message (stderr)
bridges.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
2 | #pragma GCC optimization ("O3")
|
bridges.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
3 | #pragma GCC optimization ("unroll-loops")
|
bridges.cpp: In function 'void rollback(int)':
bridges.cpp:46:21: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
46 | while(st.size() > now){
| ~~~~~~~~~~^~~~~
bridges.cpp: In function 'void oper(int, int)':
bridges.cpp:71:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | while(cur < unchange.size()){
| ~~~~^~~~~~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:100:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
100 | freopen(task".INP","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |