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;
}
Compilation message (stderr)
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/gthr.h:148,
from /usr/include/c++/10/ext/atomicity.h:35,
from /usr/include/c++/10/bits/ios_base.h:39,
from /usr/include/c++/10/ios:42,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from bridges.cpp:3:
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:102:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
102 | __gthrw(pthread_once)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:102:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:103:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
103 | __gthrw(pthread_getspecific)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:103:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:104:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
104 | __gthrw(pthread_setspecific)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:104:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:106:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
106 | __gthrw(pthread_create)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:106:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:107:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
107 | __gthrw(pthread_join)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:107:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:108:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
108 | __gthrw(pthread_equal)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:108:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:109:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
109 | __gthrw(pthread_self)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:109:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:110:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
110 | __gthrw(pthread_detach)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:110:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:112:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
112 | __gthrw(pthread_cancel)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:112:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:114:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
114 | __gthrw(sched_yield)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:114:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:116:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
116 | __gthrw(pthread_mutex_lock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:116:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:117:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
117 | __gthrw(pthread_mutex_trylock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:117:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:119:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
119 | __gthrw(pthread_mutex_timedlock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:119:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:121:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
121 | __gthrw(pthread_mutex_unlock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:121:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:122:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
122 | __gthrw(pthread_mutex_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:122:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:123:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
123 | __gthrw(pthread_mutex_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:123:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:125:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
125 | __gthrw(pthread_cond_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:125:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:126:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
126 | __gthrw(pthread_cond_broadcast)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:126:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:127:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
127 | __gthrw(pthread_cond_signal)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:127:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:128:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
128 | __gthrw(pthread_cond_wait)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:128:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:129:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
129 | __gthrw(pthread_cond_timedwait)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:129:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:130:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
130 | __gthrw(pthread_cond_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:130:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:132:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
132 | __gthrw(pthread_key_create)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:132:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:133:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
133 | __gthrw(pthread_key_delete)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:133:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:134:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
134 | __gthrw(pthread_mutexattr_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:134:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:135:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
135 | __gthrw(pthread_mutexattr_settype)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:135:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:136:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
136 | __gthrw(pthread_mutexattr_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:136:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:237:10: error: attribute value 'arch=skylake' was already specified in 'target' attribute
237 | __gthrw2(__gthrw_(__pthread_key_create),
| ^~~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:237:10: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:73:3: error: attribute value 'arch=skylake' was already specified in 'target' attribute
73 | _GLIBCXX_GTHRW(rwlock_rdlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:73:3: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:74:3: error: attribute value 'arch=skylake' was already specified in 'target' attribute
74 | _GLIBCXX_GTHRW(rwlock_tryrdlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:74:3: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:75:3: error: attribute value 'arch=skylake' was already specified in 'target' attribute
75 | _GLIBCXX_GTHRW(rwlock_wrlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:75:3: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:76:3: error: attribute value 'arch=skylake' was already specified in 'target' attribute
76 | _GLIBCXX_GTHRW(rwlock_trywrlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:76:3: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:77:3: error: attribute value 'arch=skylake' was already specified in 'target' attribute
77 | _GLIBCXX_GTHRW(rwlock_unlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:77:3: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:91:4: error: attribute value 'arch=skylake' was already specified in 'target' attribute
91 | __gthrw(pthread_rwlock_timedrdlock);
| ^~~~~~~
/usr/include/c++/10/shared_mutex:91:4: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:101:4: error: attribute value 'arch=skylake' was already specified in 'target' attribute
101 | __gthrw(pthread_rwlock_timedwrlock);
| ^~~~~~~
/usr/include/c++/10/shared_mutex:101:4: error: attribute value 'arch=skylake' was already specified in 'target' attribute
bridges.cpp: In function 'void roll_back(int)':
bridges.cpp:41:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int&, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
41 | while(his.size() > until){
| ~~~~~~~~~~~^~~~~~~
bridges.cpp: In function 'int32_t main()':
bridges.cpp:85:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for(int i = 0 ; i < ask.size() ; i++){
| ~~^~~~~~~~~~~~
bridges.cpp:86:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | while(j < un_change.size() && E[un_change[j]].w >= ask[i].a){
| ~~^~~~~~~~~~~~~~~~~~
bridges.cpp:91:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for(int k = 0; k < change.size() ; k++){
| ~~^~~~~~~~~~~~~~~
bridges.cpp:96:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for(int k = 0; k < g.size() ; k++){
| ~~^~~~~~~~~~
bridges.cpp:109:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | for(int k = 0; k < change.size() ; k++){
| ~~^~~~~~~~~~~~~~~