Submission #139745

#	Time	Username	Problem	Language	Result	Execution time	Memory
139745		FedericoS	Bridges (APIO19_bridges)	C++14	43 / 100	815 ms	14060 KiB

bridges

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,pii> pip;

bool sub1=true;
bool sub2=true;

int INF=2e9;
int N,M;
int t,x,y,z;
vector<pii> grafo[50005];
int Q;
map<int,int> W;

int ans;
bool V[50005];

int R[200005];

int S[50005];
int P[50005];
vector<pair<pii,pii> > E;
int G[100005];

void update(int a, int b, int k=1, int l=1, int r=N-1){
	if(l==r)
		R[k]=b;
	else{
		int m=(l+r)/2;
		if(a<=m)
			update(a,b,2*k,l,m);
		else
			update(a,b,2*k+1,m+1,r);
		R[k]=min(R[2*k],R[2*k+1]);
	}}
int queryR(int a, int b, int k=1, int l=1, int r=N-1){

	if(r<a)
		return N;
	else if(l==r){

		if(R[k]>=b)
			return N;
		else
			return l;
	}
	else{

		if(a<=l and R[k]>=b)
			return N;

		int m=(l+r)/2;

		int x=queryR(a,b,2*k,l,m);
		if(x!=N)
			return x;
		else
			return queryR(a,b,2*k+1,m+1,r);

	}}
int queryL(int a, int b, int k=1, int l=1, int r=N-1){

	if(a<l)
		return 0;
	else if(l==r){

		if(R[k]>=b)
			return 0;
		else
			return l;
	}
	else{

		if(r<=a and R[k]>=b)
			return 0;

		int m=(l+r)/2;

		int x=queryL(a,b,2*k+1,m+1,r);
		if(x!=0)
			return x;
		else
			return queryL(a,b,2*k,l,m);
	}}
void DFS(int k){

	if(V[k])
		return;
	V[k]=true;
	ans++;

	for(pii f:grafo[k])
		if(W[f.second]>=y)
			DFS(f.first);}

int fi(int x){
	while(x!=P[x])
		x=P[x];
	return x;
}

void un(int x, int y){

	x=fi(x);
	y=fi(y);

	if(x==y)
		return;

	if(S[x]<S[y])
		swap(x,y);

	P[y]=x;
	S[x]+=S[y];
}


int main(){

	cin>>N>>M;
	for(int i=0;i<M;i++){
		cin>>x>>y>>z;
		grafo[x].push_back({y,i+1});
		grafo[y].push_back({x,i+1});

		E.push_back({{-z,0},{x,y}});
		W[i+1]=z;
	}

	cin>>Q;
	if(sub1 and N<=1000 and M<=1000 and Q<=10000){
		while(Q--){
			cin>>t>>x>>y;
			if(t==1)
				W[x]=y;
			else{
				for(int i=1;i<N+1;i++)
					V[i]=false;
				ans=0;
				DFS(x);
				cout<<ans<<"\n";
			}
		}
	}
	else if(sub2 and M==N-1){
		for(int i=1;i<M+1;i++)
			update(i,W[i]);

		while(Q--){
			cin>>t>>x>>y;
			if(t==1){
				W[x]=y;
				update(x,W[x]);
			}
			else
				cout<<queryR(x,y)-queryL(x-1,y)<<"\n";
				//cout<<queryL(x-1,y)<<" "<<queryR(x,y)<<"\n";
		}
	}
	else{

		for(int i=1;i<N+1;i++){
			P[i]=i;
			S[i]=1;
		}

		for(int i=0;i<Q;i++){
			cin>>t>>x>>y;
			E.push_back({{-y,1},{x,i}});
		}

		sort(E.begin(),E.end());

		for(auto p:E){
			if(p.first.second)
				G[p.second.second]=S[fi(p.second.first)];
			else
				un(p.second.first,p.second.second);
		}

		for(int i=0;i<Q;i++)
			cout<<G[i]<<"\n";

	}
}

• Subtask 1: 13 / 13
• Subtask 2: 16 / 16
• Subtask 3: 0 / 17
• Subtask 4: 14 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27