Submission #996501


Source Code Expand

#include <string>
#include <vector>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;

#ifndef ___Rank_Union_Find
#define ___Rank_Union_Find

#include <vector>

// ------ Class ------ //
class UnionFind {
private:
	unsigned size_; std::vector<unsigned> par, rank;
public:
	UnionFind() : size_(0), par(std::vector<unsigned>()), rank(std::vector<unsigned>()) {};
	UnionFind(unsigned size__) : size_(size__) {
		par.resize(size_); rank.resize(size_);
		for (unsigned i = 0; i < size_; i++) par[i] = i, rank[i] = 0;
	}
	unsigned size() { return size_; }
	unsigned root(unsigned x) { return par[x] == x ? x : par[x] = root(par[x]); }
	bool same(unsigned x, unsigned y) { return root(x) == root(y); }
	void unite(unsigned x, unsigned y) {
		x = root(x), y = root(y);
		if (x == y) return;
		if (rank[x] < rank[y]) par[x] = y;
		else if (rank[x] == rank[y]) par[y] = x, rank[x]++;
		else par[y] = x;
	}
	bool operator==(const UnionFind &u) { return par == u.par; }
	bool operator!=(const UnionFind &u) { return par != u.par; }
};

#endif

#include <cstdio>
#include <algorithm>
#pragma warning(disable : 4996)
using namespace std;
struct edge { int a, b, cost; };
bool operator<(const edge& e1, const edge& e2) {
	return e1.cost < e2.cost;
}
int N, M, Q, s, t;
int main() {
	scanf("%d%d", &N, &M);
	vector<edge> e(M);
	for (int i = 0; i < M; i++) {
		scanf("%d%d%d", &e[i].a, &e[i].b, &e[i].cost);
		e[i].a--; e[i].b--;
	}
	sort(e.begin(), e.end());
	scanf("%d", &Q);
	if (Q > 3000) return 0;
	while (Q--) {
		scanf("%d%d", &s, &t); s--, t--;
		UnionFind uf(N); uf.unite(s, t);
		long long sum = 0;
		int cnt = 0;
		for (int i = 0; i < M && cnt < N - 2; i++) {
			if (!uf.same(e[i].a, e[i].b)) {
				sum += e[i].cost;
				uf.unite(e[i].a, e[i].b);
				cnt++;
			}
		}
		printf("%lld\n", sum);
	}
	return 0;
}

Submission Info

Submission Time
Task A - Graph
User square1001
Language C++14 (GCC 5.4.1)
Score 500
Code Size 1927 Byte
Status WA
Exec Time 599 ms
Memory 4992 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:50:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
                       ^
./Main.cpp:53:48: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &e[i].a, &e[i].b, &e[i].cost);
                                                ^
./Main.cpp:57:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
                 ^
./Main.cpp:60:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &s, &t); s--, t--;
                        ^

Judge Result

Set Name Sample subtask1 subtask2 All
Score / Max Score 0 / 0 200 / 200 300 / 300 0 / 200
Status
AC × 2
AC × 12
AC × 21
AC × 21
WA × 8
Set Name Test Cases
Sample sample_1.txt, sample_2.txt
subtask1 sample_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
subtask2 sample_1.txt, sample_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt
All sample_1.txt, sample_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_3_1.txt, subtask_3_2.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt
Case Name Status Exec Time Memory
sample_1.txt AC 3 ms 256 KB
sample_2.txt AC 3 ms 256 KB
subtask_1_1.txt AC 3 ms 256 KB
subtask_1_10.txt AC 67 ms 2560 KB
subtask_1_11.txt AC 3 ms 256 KB
subtask_1_2.txt AC 15 ms 768 KB
subtask_1_3.txt AC 133 ms 4992 KB
subtask_1_4.txt AC 4 ms 256 KB
subtask_1_5.txt AC 4 ms 384 KB
subtask_1_6.txt AC 35 ms 1408 KB
subtask_1_7.txt AC 133 ms 4992 KB
subtask_1_8.txt AC 4 ms 384 KB
subtask_1_9.txt AC 6 ms 384 KB
subtask_2_1.txt AC 587 ms 4992 KB
subtask_2_2.txt AC 550 ms 4992 KB
subtask_2_3.txt AC 542 ms 4992 KB
subtask_2_4.txt AC 570 ms 4992 KB
subtask_2_5.txt AC 201 ms 384 KB
subtask_2_6.txt AC 443 ms 512 KB
subtask_2_7.txt AC 454 ms 1408 KB
subtask_2_8.txt AC 599 ms 4992 KB
subtask_3_1.txt WA 133 ms 4864 KB
subtask_3_2.txt WA 133 ms 4864 KB
subtask_3_3.txt WA 4 ms 256 KB
subtask_3_4.txt WA 6 ms 384 KB
subtask_3_5.txt WA 67 ms 2560 KB
subtask_3_6.txt WA 100 ms 3712 KB
subtask_3_7.txt WA 133 ms 4864 KB
subtask_3_8.txt WA 133 ms 4864 KB