제출 #568996

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
568996		_karan_gandhi	다리 (APIO19_bridges)	C++17	14 / 100	96 ms	6324 KiB

bridges

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define all(v) v.begin(), v.end()
#define endl '\n'
#define pl(var) " [" << #var << ": " << (var) << "] "

template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "[" << p.first << ", " << p.second << "]"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) { cout << "["; for(int i = 0; i < (int)v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) { cin >> p.first; return cin >> p.second; }

struct DSU { // Sorry UFDS
	vector<int> p, s;
	int components;

	void init(int n) {
		p = vector<int>(n);
		iota(all(p), 0);
		s = vector<int>(n, 1);
		components = n;
	}

	int get(int x) {
		return p[x] = (p[x] == x ? x : get(p[x]));
	}

	void unite(int a, int b) {
		a = get(a);
		b = get(b);

		if (a == b) return;

		if (s[a] > s[b]) swap(a, b);

		p[a] = b;
		s[b] += s[a];
		components--;
	}

	bool same_set(int a, int b) {
		return get(a) == get(b);
	}

	int size(int x) {
		return s[get(x)];
	}
};


void solve() {
	int n, m; cin >> n >> m;

	vector<pair<int, pair<int, int>>> edges;

	for (int i = 0; i < m; i++) {
		int a, b, c; cin >> a >> b >> c;
		a--, b--;
		edges.emplace_back(c, make_pair(a, b));
	}

	sort(all(edges));

	DSU dsu;
	dsu.init(n);
	int q; cin >> q;
	vector<pair<pair<int, int>, int>> queries;

	for (int i = 0; i < q; i++) {
		int c; cin >> c;
		int a, b; cin >> a >> b;
		if (c == 1) continue;
		a--;
		queries.emplace_back(make_pair(b, a), i);
	}

	// cout << queries << endl;

	sort(all(queries));
	vector<int> ans(q);
	int ptr = 0;
	reverse(all(edges));
	reverse(all(queries));
	// cout << pl(q) << endl;
	for (int i = 0; i < queries.size(); i++) {
		while (ptr < m && edges[ptr].first >= queries[i].first.first) {
			dsu.unite(edges[ptr].second.first, edges[ptr].second.second);
			ptr++;
		}
		// cout << pl(queries[i]) << endl;
		// cout << pl(i) << endl;
		// cout << pl(dsu.size(queries[i].first.second)) << endl;
		// cout << pl(queries[i].second) << endl;
		ans[queries[i].second] = dsu.size(queries[i].first.second);
		// cout << pl(ans[queries[i].second]) << endl;
	}

	for (int i : ans) cout << i << endl;
}

int main() {
#ifdef LOCAL
    auto clock_start = chrono::high_resolution_clock::now();
    cout << endl;
#endif

	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int T = 1;
	// cin >> T;
	while (T--) 
		solve();

#ifdef LOCAL
    auto clock_end = chrono::high_resolution_clock::now();
    cout << endl;
    chrono::duration<double> elapsed = clock_end - clock_start;
    cout << "Execution time: " << elapsed.count() << "s" << endl;
#endif

	return 0;
}

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

bridges.cpp: In function 'void solve()':
bridges.cpp:85:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |  for (int i = 0; i < queries.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~

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