#include <bits/stdc++.h>
#define fi first
#define se second
const int B = 400;
const int N = 5e4 + 11;
const int M = 1e5 + 11;
using namespace std;
struct DSU{
vector<pair<int, int>> hist;
int dsu[N], sz[N];
void init(int n) { for(int i = 0; i <= n; i++) dsu[i] = i, sz[i] = 1; }
int f(int x) { return x == dsu[x] ? x : f(dsu[x]); }
int get_size(int x) { return sz[f(x)]; }
void g(int x, int y) {
x = f(x), y = f(y);
if(x == y) { hist.push_back({-1, -1}); return; }
if(sz[x] < sz[y]) swap(x, y);
sz[x] += sz[y]; dsu[y] = x;
hist.push_back({x, y});
}
void back(){
pair<int, int> p = hist.back(); hist.pop_back();
if(p.fi == -1) return;
sz[p.fi] -= sz[p.se];
dsu[p.se] = p.se;
}
} dsu;
vector<pair<int, int>> vp;
int w[M];
struct query{
int t, a, b, ans;
};
struct edge{
int u, v, w;
};
struct range{
int l, r, e;
};
vector<query> Q;
vector<edge> E;
void add_edge(int m){
E.clear();
for(int i = 0; i < m; i++){
E.push_back({vp[i].fi, vp[i].se, w[i]});
}
sort(E.begin(), E.end(), [](edge a, edge b){
return a.w < b.w;
});
}
vector<int> T[N << 2];
void add(int t, int l, int r, int ql, int qr, int qv){
if(r < ql || qr < l) return;
if(ql <= l && r <= qr) {
T[t].push_back(qv);
return;
}
int m = (l + r) / 2;
add(t << 1, l, m, ql, qr, qv);
add(t << 1 | 1, m + 1, r, ql, qr, qv);
}
vector<int> ans;
vector<int> t1; vector<pair<int, int>> t2;
int n, m;
void dfs(int t, int l, int r){
for(auto i : T[t]){
dsu.g(vp[i].fi, vp[i].se);
}
if(l == r){
if(l < t2.size()){
int a = dsu.get_size(Q[t2[l].fi].a);
ans.push_back(a);
}
}else{
int m = (l + r) / 2;
dfs(t << 1, l, m);
dfs(t << 1 | 1, m + 1, r);
}
for(auto i : T[t]){
dsu.back();
}
}
int main(){
cin >> n >> m;
vp.push_back({});
for(int i = 1; i <= m; i++){
int u, v, _w;
cin >> u >> v >> _w;
vp.push_back({u, v});
w[i] = _w;
}
int q; cin >> q;
for(int i = 0; i < q; i++){
int t, a, b;
cin >> t >> a >> b;
Q.push_back({t, a, b});
}
for(int i = 0; i < q; i += B){
add_edge(m); dsu.init(n);
t1.clear(); t2.clear();
int id_t2 = 0;
for(int j = i; j < min(q, i + B); j++){
if(Q[j].t == 1) t1.push_back(j);
else t2.push_back({j, id_t2++});
}
bool u[M] = {}; int spi[M] = {}, w[M] = {}; for(int j = 1; j <= m; j++) w[j] = ::w[j];
vector<int> sp; for(int j = 0; j < t1.size(); j++) sp.push_back(Q[t1[j]].a), spi[Q[t1[j]].a] = j, u[Q[t1[j]].a] = true;
sort(sp.begin(), sp.end()); sp.resize(unique(sp.begin(), sp.end()) - sp.begin());
vector<range> ranges;
int id = 0;
for(int k = 0; k < t2.size(); k++){
while(id < t1.size() && t1[id] < t2[k].fi) w[Q[t1[id]].a] = Q[t1[id]].b, id++;
for(int j = 0; j < sp.size(); j++){
if(w[sp[j]] >= Q[t2[k].fi].b){
ranges.push_back({k, k, sp[j]});
}
}
}
sort(t2.begin(), t2.end(), [](pair<int, int> x, pair<int, int> y){
return Q[x.fi].b > Q[y.fi].b;
});
int mp[B];
for(int i = 0; i < t2.size(); i++) mp[t2[i].se] = i;
for(auto r : ranges){
add(1, 0, B, mp[r.l], mp[r.r], r.e);
}
for(int j = 1; j <= m; j++){
if(u[j]) continue;
int l = 0, r = (int) t2.size();
while(l != r){
int m = (l + r) / 2;
if(Q[t2[m].fi].b > ::w[j]){
l = m + 1;
}else{
r = m;
}
}
add(1, 0, B, l, B, j);
}
ans.clear();
dfs(1, 0, B - 1);
for(int j = 0; j < t2.size(); j++){
Q[t2[j].fi].ans = ans[j];
}
for(int j = i; j < min(q, i + B); j++){
if(Q[j].t == 1){
w[Q[j].a] = Q[j].b;
}
}
}
for(int i = 0; i < q; i++){
if(Q[i].t == 2){
cout << Q[i].ans << endl;
}
}
}
Compilation message
bridges.cpp: In function 'void dfs(int, int, int)':
bridges.cpp:79:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | if(l < t2.size()){
| ~~^~~~~~~~~~~
bridges.cpp:88:11: warning: unused variable 'i' [-Wunused-variable]
88 | for(auto i : T[t]){
| ^
bridges.cpp: In function 'int main()':
bridges.cpp:118:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
118 | vector<int> sp; for(int j = 0; j < t1.size(); j++) sp.push_back(Q[t1[j]].a), spi[Q[t1[j]].a] = j, u[Q[t1[j]].a] = true;
| ~~^~~~~~~~~~~
bridges.cpp:122:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for(int k = 0; k < t2.size(); k++){
| ~~^~~~~~~~~~~
bridges.cpp:123:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
123 | while(id < t1.size() && t1[id] < t2[k].fi) w[Q[t1[id]].a] = Q[t1[id]].b, id++;
| ~~~^~~~~~~~~~~
bridges.cpp:124:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
124 | for(int j = 0; j < sp.size(); j++){
| ~~^~~~~~~~~~~
bridges.cpp:134:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
134 | for(int i = 0; i < t2.size(); i++) mp[t2[i].se] = i;
| ~~^~~~~~~~~~~
bridges.cpp:153:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
153 | for(int j = 0; j < t2.size(); j++){
| ~~^~~~~~~~~~~
bridges.cpp:117:23: warning: variable 'spi' set but not used [-Wunused-but-set-variable]
117 | bool u[M] = {}; int spi[M] = {}, w[M] = {}; for(int j = 1; j <= m; j++) w[j] = ::w[j];
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5460 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5460 KB |
Output is correct |
| 3 |
Incorrect |
185 ms |
9708 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3021 ms |
70532 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3054 ms |
63424 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3035 ms |
68588 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3021 ms |
70532 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5460 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5460 KB |
Output is correct |
| 3 |
Incorrect |
185 ms |
9708 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
