Submission #154726

#	Time	Username	Problem	Language	Result	Execution time	Memory
154726		Pro_ktmr	Bridges (APIO19_bridges)	C++14	13 / 100	3087 ms	20448 KiB

bridges

#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define MP make_pair

int N,M,Q;
pair<int,int> bridge[100000];
vector<pair<int,int>> edge[50000];
vector<int> edgeNum[500000];

int main(){
	cin >> N >> M;
	for(int i=0; i<M; i++){
		int a, b, c;
		cin >> a >> b >> c;
		bridge[i] = MP(a-1, b-1);
		edge[a-1].push_back(MP(b-1,c));
		edgeNum[a-1].push_back(i);
		edge[b-1].push_back(MP(a-1,c));
		edgeNum[b-1].push_back(i);
	}
	cin >> Q;
	for(int i=0; i<Q; i++){
		int t, a, b;
		cin >> t >> a >> b;
		if(t == 1){
			int c = b;
			int n = a-1;
			a = bridge[n].first;
			b = bridge[n].second;
			for(int j=0; j<edge[a].size(); j++){
				if(edgeNum[a][j] == n) edge[a][j].second = c;
			}
			for(int j=0; j<edge[b].size(); j++){
				if(edgeNum[b][j] == n) edge[b][j].second = c;
			}
		}
		else{
			int w = b;
			int p = a-1;
			bool visited[100000] = {};
			visited[p] = true;
			queue<int> que;
			que.push(p);
			while(!que.empty()){
				int now = que.front();
				que.pop();
				for(int j=0; j<edge[now].size(); j++){
					if(edge[now][j].second < w) continue;
					if(!visited[edge[now][j].first]){
						visited[edge[now][j].first] = true;
						que.push(edge[now][j].first);
					}
				}
			}
			int ans = 0;
			for(int j=0; j<N; j++){
				if(visited[j]) ans++;
			}
			cout << ans << endl;
		}
	}
	
	return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:31:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0; j<edge[a].size(); j++){
                 ~^~~~~~~~~~~~~~~
bridges.cpp:34:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0; j<edge[b].size(); j++){
                 ~^~~~~~~~~~~~~~~
bridges.cpp:48:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0; j<edge[now].size(); j++){
                  ~^~~~~~~~~~~~~~~~~

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