#include<bits/stdc++.h>
using namespace std;
bool M1;
#define PI 3.14159265358979323846
#define sz(a) (int)a.size()
#define all(x) x.begin(),x.end()
#define ii pair<int,int>
#define iii pair<int,ii>
#define iv pair<ii,ii>
#define se second
#define fi first
#define ffi fi.fi
#define sfi se.fi
#define sse se.se
#define fse fi.se
#define lt(i, c, d) for(int i = c; i <= d; ++i)
#define fl(i, c, d) for(int i = d; i >= c; --i)
#define pb push_back
#define emb emplace_back
#define emf emplace_front
#define em emplace
#define look_memory cerr<<abs(&M2-&M1)/1024.0/1024<<'\n'
#define look_time cerr << "TIME : " << clock() * 0.001 << "s" <<'\n'
const int N=1e6+5,lg=30,mod=1e9+7,block=600;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int u,int v){
return u+rd()%(v-u+1);
}
int dx[]={1,0,-1,0,1,1,-1,-1};
int dy[]={0,-1,0,1,1,-1,1,-1};
int node,query,edge,ans[N];
struct DSUrollback {
struct State {
int u, v, rku, rkv, timer,szu,szv;
};
int n;
vector<int> par, rk,siz;
vector<State> history;
DSUrollback() : n(0) {}
DSUrollback(int _n) : n(_n), par(_n + 5), rk(_n + 5, 0), siz(n+5,1){
history.clear();
for (int i = 1; i <= n; ++i) par[i] = i;
}
void build(int _n) {
*this = DSUrollback(_n);
}
int acs(int u) {
while (par[u] != u) u = par[u];
return u;
}
bool join(int u, int v, int timer) {
u = acs(u);
v = acs(v);
if (u == v) return false;
if (rk[u] < rk[v]) std::swap(u, v);
history.push_back({u, v, rk[u], rk[v], timer,siz[u],siz[v]});
siz[u]+=siz[v];
par[v] = u;
if (rk[u] == rk[v]) rk[u]++;
return true;
}
void rollback(int timer) {
while (!history.empty() && history.back().timer >= timer) {
State s = history.back(); history.pop_back();
par[s.u] = s.u;
par[s.v] = s.v;
rk[s.u] = s.rku;
rk[s.v] = s.rkv;
siz[s.u]=s.szu;
siz[s.v]=s.szv;
}
}
};
struct pt{
int u,v,w;
}b[N];
struct pt1{
int t,x,y;
}truyvan[N];
vector<int>nen,capnhat[N];
vector<int>req[N];
int last[N],truoc[N];
bool M2;
void solve(){
cin >> node >> edge;
for(int i=1;i<=edge;++i){
cin >> b[i].u >> b[i].v >> b[i].w;
nen.emb(b[i].w);
}
int query;
cin >> query;
for(int i=1;i<=query;++i){
int t,x,y;
cin >> t >> x >> y;
truyvan[i]={t,x,y};
nen.emb(y);
}
sort(all(nen));
nen.erase(unique(all(nen)),nen.end());
for(int i=1;i<=edge;++i){
b[i].w=lower_bound(all(nen),b[i].w)-nen.begin()+1;
}
for(int i=1;i<=query;++i){
truyvan[i].y=lower_bound(all(nen),truyvan[i].y)-nen.begin()+1;
if(truyvan[i].t==2){
truoc[i]=last[truyvan[i].x];
last[truyvan[i].x]=i;
}
}
int n=sz(nen);
for(int _=1;_<=query;_+=block){
int L=_;
int R=min(query,_+block-1);
vector<int>t1;
vector<int>vis(edge+5,0),k1(edge+5,0);
for(int i=L;i<=R;++i){
auto [t,x,y]=truyvan[i];
if(t==2){
capnhat[y].emb(i);
}
else{
vis[x]=true;
t1.emb(i);
}
}
for(int i=1;i<=edge;++i){
if(!vis[i])
req[b[i].w].emb(i);
}
DSUrollback dsu(node);
int j=0;
for(int i=n;i>=1;--i){
for(auto x:req[i]){
if(!vis[x])
dsu.join(b[x].u,b[x].v,-1);
}
for(auto x:capnhat[i]){
// cout <<i<<" "<<x<<'\n';
for(int j:t1){
if(j>x)break;
k1[truyvan[j].x]=j;
}
for(int j:t1){
if(truyvan[k1[truyvan[j].x]].y){
auto [t,u,v]=truyvan[k1[truyvan[j].x]];
// cout <<b[u].u<<" "<<b[u].v<<" "<<b[u].w<<" "<<i<<'\n';
if(v>=i)
dsu.join(b[u].u,b[u].v,1);
}
else{
auto [t,u,v]=truyvan[j];
if(b[u].w>=i){
dsu.join(b[u].u,b[u].v,1);
}
}
}
ans[x]=dsu.siz[dsu.acs(truyvan[x].x)];
dsu.rollback(0);
for(int j:t1){
if(j>x)break;
k1[truyvan[j].x]=j;
}
}
capnhat[i].clear();
req[i].clear();
}
for(auto i:t1){
auto [t,x,y]=truyvan[i];
b[x].w=y;
}
}
for(int i=1;i<=query;++i)if(truyvan[i].t==2)cout << ans[i]<<'\n';
}
main()
{
srand(time(0));
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#define task "aws"
if(fopen(task".inp","r")){
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
int t=1;
// cin >> t;
while(t--){
solve();
}
look_memory;
look_time;
}
Compilation message (stderr)
bridges.cpp:189:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
189 | main()
| ^~~~
bridges.cpp: In function 'int main()':
bridges.cpp:197:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
197 | freopen(task".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:198:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
198 | freopen(task".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# | 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... |