oj.uz

답안 #568996

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
568996 2022-05-26T13:08:47 Z _karan_gandhi 다리 (APIO19_bridges) C++17
14 / 100
 96 ms 6324 KB 
#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;
}

Compilation message

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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 60 ms 3432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 68 ms 3208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 96 ms 6324 KB Output is correct
2 Correct 43 ms 2936 KB Output is correct
3 Correct 40 ms 2684 KB Output is correct
4 Correct 45 ms 2620 KB Output is correct
5 Correct 75 ms 4976 KB Output is correct
6 Correct 81 ms 5488 KB Output is correct
7 Correct 76 ms 4924 KB Output is correct
8 Correct 60 ms 3956 KB Output is correct
9 Correct 59 ms 3916 KB Output is correct
10 Correct 60 ms 4128 KB Output is correct
11 Correct 82 ms 4616 KB Output is correct
12 Correct 85 ms 4800 KB Output is correct
13 Correct 68 ms 4668 KB Output is correct
14 Correct 72 ms 4924 KB Output is correct
15 Correct 73 ms 4920 KB Output is correct
16 Correct 81 ms 5424 KB Output is correct
17 Correct 88 ms 5440 KB Output is correct
18 Correct 81 ms 5436 KB Output is correct
19 Correct 81 ms 5408 KB Output is correct
20 Correct 76 ms 4816 KB Output is correct
21 Correct 82 ms 4800 KB Output is correct
22 Correct 79 ms 5116 KB Output is correct
23 Correct 69 ms 4648 KB Output is correct

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 60 ms 3432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -