제출 #1044800

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1044800		vjudge1	다리 (APIO19_bridges)	C++17	14 / 100	58 ms	8264 KiB

bridges

#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
using namespace std;
vector <int> par, w;

int parent(int node) {
	if(par[node] == node) return node;
	return par[node] = parent(par[node]);
}

void dsu(int a, int b) {
	a = parent(a);
	b = parent(b);
	if(a == b) return;
	if(w[a] < w[b]) swap(a, b);
	// a ya byi ekle
	w[a] += w[b];
	par[b] = par[a];
}

int32_t main(){
	fast
	int n, m;
	cin >> n >> m;
	vector <array<int, 3> > edges;
	for(int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		edges.push_back({c, a, b});
	}
	int q;
	cin >> q;
	vector <array<int, 3> > queries;
	for(int i = 0; i < q; i++) {
		int type, a, b;
		cin >> type >> a >> b;
		queries.push_back({b, a, i});
	}
	{
		sort(queries.begin(), queries.end());
		sort(edges.begin(), edges.end());
		reverse(queries.begin(), queries.end());
		reverse(edges.begin(), edges.end());
	}
	par.resize(n + 1);
	w.resize(n + 1);
	for(int i = 1; i <= n; i++) par[i] = i, w[i] = 1;

	vector <int> ans(q);
	int it = 0;
	for(auto [we, from, ind]:queries) {
		while(it < edges.size() and edges[it][0] >= we) {
			dsu(edges[it][1], edges[it][2]);
			it++;
		}
		ans[ind] = w[parent(from)];
	}
	for(int i = 0; i < q; i++) {
		cout << ans[i] << "\n";
	}
}

컴파일 시 표준 에러 (stderr) 메시지

bridges.cpp: In function 'int32_t main()':
bridges.cpp:54:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   while(it < edges.size() and edges[it][0] >= we) {
      |         ~~~^~~~~~~~~~~~~~

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