#include <bits/stdc++.h>
//#define int ll
#define MAX 1000001
#define INF INT_MAX
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ins insert
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define lb(a,b) lower_bound(all(a),b)
#define ub(a,b) upper_bound(all(a),b)
#define sortv(a) sort(all(a))
#define outputar(a,b){\
for(int i=0;i<b;i++){\
cout << a[i] << " ";\
}\
cout << "\n";\
}
#define outputvec(a){\
for(auto x:a){\
cout << (int)x << " ";\
}\
cout << endl;\
}
#define reset(a,n,v){\
for(int i=0;i<n;i++){\
a[i]=v;\
}\
}
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef tuple<ll,ll,ll> tll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef double db;
typedef long double ldb;
inline void USACO(string filename){
freopen((filename+".in").c_str(),"r",stdin);
freopen((filename+".out").c_str(),"w",stdout);
}
int n,q,t=1,m,k,x,y,z,x2,y2,z2,a[MAX],b[MAX],e[MAX],ans[MAX],res;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
string s[MAX],str[1];
//int e[1001][1001];
//bool e1[1001][1001];
string s1,s2,s3;
const int mod = 998244353;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
struct DSU{
vector<int> e;
DSU(int N){ e=vector<int>(N+1,-1);}
void init(int N){e=vector<int>(N+1,-1);}
int get(int x){return e[x]<0 ? x : e[x]=get(e[x]);}
bool same_set(int x,int y){ return get(x)==get(y);}
int size(int x){return -e[get(x)];}
bool unite(int x,int y){
x=get(x);
y=get(y);
if(x==y) return false;
if(e[x]>e[y]) swap(x,y);
e[x]+=e[y]; e[y]=x;
return true;
}
};
DSU dsu(n);
const int sz=450;
vector<vector<int>> g;
void dfs(int v){
b[v]=1;
res+=dsu.size(v);
for(auto x:g[v]){
if(b[x]==1){
continue;
}
dfs(x);
}
}
void solve(){
cin >> n >> m;
vector<array<int,3>> d,d1;
set<array<int,4>> c;
vector<array<int,4>> c1;
g.clear();
g.resize(n+1);
for(int i=0;i<m;i++){
cin >> x >> y >> z;
x--;
y--;
c.ins({z,x,y,i});
c1.pb({z,x,y,i});
}
cin >> q;
for(int i=0;i<q;i++){
cin >> x >> y >> z;
y--;
d.pb({x,y,z});
}
int l=0;
while(l<q){
dsu.init(n);
int r=min(l+sz,q);
for(int i=0;i<m;i++){
a[i]=0;
}
for(int i=l;i<r;i++){
if(d[i][0]==1){
a[d[i][1]]=1;
}
else{
d1.pb({d[i][2],d[i][1],i});
}
}
sortv(d1);
reverse(all(d1));
auto it=c.rbegin();
for(auto x:d1){
res=0;
while(it!=c.rend() && (*it)[0]>=x[0]){
if(a[(*it)[3]]==1){
++it;
continue;
}
dsu.unite((*it)[1],(*it)[2]);
//cout << (*it)[1] << " " << (*it)[2] << " z" << endl;
++it;
}
for(int i=l;i<r;i++){
if(d[i][0]==1){
e[d[i][1]]=0;
}
}
vector<array<int,2>> del;
//cout << x[0] << " " << x[1] << " " << x[2] << " h" << endl;
for(int i=x[2];i>=l;i--){
if(d[i][0]==1 && e[d[i][1]]==0){
e[d[i][1]]=1;
if(d[i][2]>=x[0]){
array<int,4> p=c1[d[i][1]];
//cout << d[i][1] << " " << p[1] << " " << p[2] << endl;
p[1]=dsu.get(p[1]);
p[2]=dsu.get(p[2]);
//cout << p[1] << " " << p[2] << endl;
b[p[1]]=0;
b[p[2]]=0;
g[p[1]].pb(p[2]);
g[p[2]].pb(p[1]);
del.pb({p[1],p[2]});
}
}
}
for(int i=x[2];i<r;i++){
if(d[i][0]==1 && e[d[i][1]]==0){
e[d[i][1]]=1;
if(c1[d[i][1]][0]>=x[0]){
array<int,4> p=c1[d[i][1]];
//cout << d[i][1] << " " << p[1] << " " << p[2] << endl;
p[1]=dsu.get(p[1]);
p[2]=dsu.get(p[2]);
//cout << p[1] << " " << p[2] << endl;
b[p[1]]=0;
b[p[2]]=0;
g[p[1]].pb(p[2]);
g[p[2]].pb(p[1]);
del.pb({p[1],p[2]});
}
}
}
b[dsu.get(x[1])]=0;
dfs(dsu.get(x[1]));
ans[x[2]]=res;
for(auto y:del){
g[y[0]].pop_back();
g[y[1]].pop_back();
}
}
for(int i=l;i<r;i++){
if(d[i][0]==1){
c.erase(c1[d[i][1]]);
c1[d[i][1]][0]=d[i][2];
c.ins(c1[d[i][1]]);
}
}
l=r;
}
for(int i=0;i<q;i++){
if(d[i][0]==2){
cout << ans[i] << "\n";
}
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//cin >> t;
ll cnt1=1;
while(t--){
solve();
}
}
Compilation message
bridges.cpp: In function 'int main()':
bridges.cpp:201:8: warning: unused variable 'cnt1' [-Wunused-variable]
201 | ll cnt1=1;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
39516 KB |
Output is correct |
| 2 |
Correct |
9 ms |
39520 KB |
Output is correct |
| 3 |
Incorrect |
773 ms |
40212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3020 ms |
51428 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3031 ms |
49264 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3024 ms |
56512 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3020 ms |
51428 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
39516 KB |
Output is correct |
| 2 |
Correct |
9 ms |
39520 KB |
Output is correct |
| 3 |
Incorrect |
773 ms |
40212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
