Submission #618975

#	Time	Username	Problem	Language	Result	Execution time	Memory
618975		Warinchai_s	Bridges (APIO19_bridges)	C++14	0 / 100	3074 ms	14624 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
int main(){
	int x,m;
	cin>>x>>m;
	int n[m][3];
	for(int i=0;i<m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		n[i][0]=a;
		n[i][1]=b;
		n[i][2]=c;
	}
	int q;
	cin>>q;
	while(q){
		int c;
		cin>>c;
		if(c==1){
			int i;
			cin>>i;
			int w;
			cin>>w;
			n[i-1][2]=w;
		}else{
			vector<pair<int,int> >v[x+1];
			queue<int>q;
			//cout<<"work";
			for(int i=0;i<m;i++){
				int f=n[i][0],s=n[i][1],t=n[i][2];
				v[f].push_back({s,t});
				v[s].push_back({f,t});
			}
			//cout<<"work";
			int w,s;
			cin>>s>>w;
			int vis[x+1]={};
			q.push(s);
			vis[s]=1;
			int ans=0;
			//cout<<"work";
			while(!q.empty()){
				//cout<<"q:"<<q.front()<<" ";
				ans++;
				int node=q.front();
				q.pop();
				if(v[node][0].second>=w&&vis[v[node][0].first]==0){
					//cout<<"v1:"<<v[node][0].first<<" ";
					vis[v[node][0].first]=1;
					q.push(v[node][0].first);
				}
				if(v[node][1].second>=w&&vis[v[node][1].first]==0&&v[node].size()==2){
					//cout<<"v2:"<<v[node][1].first<<" ";
					vis[v[node][1].first]=1;
					q.push(v[node][1].first);
				}
			}
			cout<<ans<<endl;
		}
		q--;
	}
}
/*
4 3
1 2 3
2 4 4
3 4 4
3
*/

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