Submission #1352985

#TimeUsernameProblemLanguageResultExecution timeMemory
1352985ezzzayBridges (APIO19_bridges)C++20
14 / 100
157 ms13012 KiB
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
const int N=3e5+5;
int sbtr[N];
int par[N];
int find(int x){
	if(x==par[x])return x;
	return par[x]=find(par[x]);
}
void merge(int a, int b){
	a=find(a);
	b=find(b);
	if(a==b)return;
	if(sbtr[a]<sbtr[b])swap(a,b);
	
	sbtr[a]+=sbtr[b];
	par[b]=a;
}
int ans[N];
signed main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		par[i]=i;
		sbtr[i]=1;
	}
	vector<vector<int>>vc,qr;
	for(int i=0;i<m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		vc.pb({c,a,b});
	}
	int q;
	cin>>q;
	for(int i=0;i<q;i++){
		int t,x,w;
		cin>>t>>x>>w;
		qr.pb({w,x,i});
	}
	// vc ni ihese qr ni bas ihese
	sort(vc.begin(),vc.end());
	reverse(vc.begin(),vc.end());
	sort(qr.begin(),qr.end());
	reverse(qr.begin(),qr.end());
	int l=0;
	for(int i=0;i<q;i++){
		int w=qr[i][0], x=qr[i][1],idx=qr[i][2];
		while(l<m and vc[l][0]>=w){
			int a=vc[l][1],b=vc[l][2];
			merge(a,b);
			l++;
		}
		ans[idx]=sbtr[find(x)];
	}	
	for(int i=0;i<q;i++)cout<<ans[i]<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...