oj.uz

Submission #618975

# Submission time Handle Problem Language Result Execution time Memory
618975 2022-08-02T08:43:20 Z Warinchai_s Bridges (APIO19_bridges) C++14
0 / 100
 3000 ms 14624 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3074 ms 5084 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3065 ms 3728 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 1652 ms 14624 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3074 ms 5084 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -