Submission #139729

#	Time	Username	Problem	Language	Result	Execution time	Memory
139729		FedericoS	Bridges (APIO19_bridges)	C++14	16 / 100	594 ms	22060 KiB

bridges

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

bool sub1=false;
bool sub2=true;

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

int ans;
bool V[50005];

int P[50005];
int R[200005];

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 stampa(int k=1, int l=1, int r=N-1){
	if(k==1)cout<<"------\n";
	cout<<k<<" "<<l<<"-"<<r<<": "<<R[k]<<endl;
	if(l!=r){
		int m=(l+r)/2;
		stampa(2*k,l,m);
		stampa(2*k+1,m+1,r);
	}
	if(k==1)cout<<"------\n";
}

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 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});

		W[i+1]=z;
		S[{x,y}]=i+1;
		S[{y,x}]=i+1;
	}

	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";
		}
	}
}

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