#include <bits/stdc++.h>
using namespace std;
#define ll int
#define pll pair<int, int>
#define pb push_back
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
const ll N = 3e5 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 350;
ll n,m,q;
struct edge{ll u,v,c,idx;} e[N], b[N];
struct query{ll typ,x,y;} t[N];
struct ccjv{ll s,w,idx;};
ll cnt[N], res[N], used[N], cost[N], mn[N];
struct dsu{
ll n;
struct snap{ll v, u, lst_par, lst_sz;};
vector<ll>p, sz;
vector<snap>g;
void init(ll _n){
n = _n;
p.resize(n + 10); sz.resize(n + 10);
g.clear();
for(int i = 1; i <= n;i++) p[i] = i, sz[i] = 1;
}
ll find(ll v){
return (v == p[v] ? v : find(p[v]));
}
void join(ll u, ll v){
u = find(u), v = find(v);
if(u == v) return;
if(sz[u] < sz[v]) swap(u, v);
g.pb({v, u, p[v], sz[u]});
p[v] = u, sz[u] += sz[v];
}
void reset(){g.clear();}
void roll_back(){
while(g.size()){
ll u = g.back().u, v = g.back().v, lst_par = g.back().lst_par, lst_sz = g.back().lst_sz;
p[v] = lst_par, sz[u] = lst_sz;
g.pop_back();
}
}
} dsu;
void to_thic_cau(){
cin >> n >> m;
for(int i = 1; i <= m;i++) {
cin >> e[i].u >> e[i].v >> e[i].c;
e[i].idx = i; cost[i] = e[i].c;
b[i] = e[i];
}
cin >> q;
for(int i = 1; i <= q;i++) cin >> t[i].typ >> t[i].x >> t[i].y;
for(int i = 1; i <= q;i += block){
sort(e + 1, e + m + 1, [&](const edge &a, const edge &b){
return cost[a.idx] > cost[b.idx];
});
dsu.init(n);
vector<ccjv>ask;
vector<ll>c;
for(int i = 1; i <= m;i++) used[i] = 0, mn[i] = inf;
for(int j = i; j <= min(q, i + block - 1);j++){
if(t[j].typ == 1) c.pb(j), used[t[j].x] = 1, mn[t[j].x] = min(mn[t[j].x], j);
else ask.pb({t[j].x, t[j].y, j});
}
sort(all(ask), [&](const ccjv &a, const ccjv &b){
return a.w > b.w;
});
sort(all(c), greater<ll>());
ll j = 1;
for(auto x : ask){
ll u = x.s, w = x.w, idx = x.idx;
while(j <= m && cost[e[j].idx] >= w){
if(!used[e[j].idx]) {
dsu.join(e[j].u, e[j].v);
}
j++;
}
dsu.reset();
for(auto k : c){
if(k > idx) continue;
ll cur = t[k].x, val = t[k].y;
if(used[cur] == 2) continue;
used[cur] = 2;
if(val >= w) {
dsu.join(b[cur].u, b[cur].v);
}
};
for(int dm = (ll)c.size() - 1; dm >= 0;dm--){
ll k = c[dm];
ll cur = t[k].x, val = t[k].y;
if(mn[cur] > idx && used[cur] == 1 && cost[cur] >= w){
used[cur] = 2;
dsu.join(b[cur].u, b[cur].v);
}
}
for(auto k : c) used[t[k].x] = 1;
res[idx] = dsu.sz[dsu.find(u)];
dsu.roll_back();
}
for(int dm = (ll)c.size() - 1; dm >= 0;dm--){
ll k = c[dm];
cost[t[k].x] = t[k].y;
}
}
for(int i = 1; i <= q;i++) if(res[i]) cout << res[i] << '\n';
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll tc = 1;
//cin >> tc;
while(tc--) to_thic_cau();
}
Compilation message
examination.cpp:12:16: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
12 | const ll inf = 1e18;
| ^~~~
examination.cpp: In function 'void to_thic_cau()':
examination.cpp:96:22: warning: unused variable 'val' [-Wunused-variable]
96 | ll cur = t[k].x, val = t[k].y;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
439 ms |
8536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
439 ms |
8536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
