Submission #136671

#	Time	Username	Problem	Language	Result	Execution time	Memory
136671		KLPP	Bridges (APIO19_bridges)	C++14	13 / 100	224 ms	4948 KiB

bridges

#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)

int main(){
  int n,m,q;
  cin>>n>>m;
  lld edgelist[m][3];
  rep(i,0,m){
    rep(j,0,3){
      cin>>edgelist[i][j];
      if(j<2)edgelist[i][j]--;
    }
  }
  cin>>q;
  if(n<=1000 && m<=1000 && q<=10000){
    while(q--){
      int type;
      cin>>type;
      if(type==1){
	int num;
	lld val;
	cin>>num>>val;
	num--;
	edgelist[num][2]=val;
      }else{
	int start;
	lld w;
	cin>>start>>w;
	start--;
	vector<int> nei[n];
	bool visited[n];
	rep(i,0,n)visited[i]=false;
	//cout<<start<<endl;
	rep(i,0,m){
	  if(edgelist[i][2]>=w){
	    //cout<<edgelist[i][0]<<" "<<edgelist[i][1]<<endl;
	    nei[edgelist[i][0]].push_back(edgelist[i][1]);
	    nei[edgelist[i][1]].push_back(edgelist[i][0]);
	  }
	}
	queue<int> q;
	q.push(start);
	visited[start]=true;
	while(!q.empty()){
	  int u=q.front();q.pop();
	  trav(v,nei[u]){
	    if(!visited[v]){
	      visited[v]=true;
	      q.push(v);
	    }
	  }
	}
	lld ans=0;
	rep(i,0,n)ans+=visited[i];
	cout<<ans<<endl;
      }
    }
  }
  return 0;
}

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