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