Submission #1026555
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif
const int inf=1e9;
const int64_t inf64=1e18;
const double eps=1e-9;
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
os << "[";
for (const auto &v : vec) {
os << v << ",";
}
os << "]";
return os;
}
class union_find{
private:
vector<int> parent,rank,gs;
int size;
public:
int count_group;
union_find()=default;
union_find(int n){ init(n); }
void init(int n){
size=n;
count_group=n;
parent.resize(size);
rank.assign(size,0);
gs.assign(size,1);
for(int i=0; i<size; ++i) parent[i]=i;
}
int find(int x){
if(parent[x]==x) return x;
else return parent[x]=find(parent[x]);
}
void unite(int x,int y){
x=find(x);
y=find(y);
if(x==y) return;
if(rank[x]<rank[y]){
parent[x]=y;
gs[y]+=gs[x];
} else {
parent[y]=x;
gs[x]+=gs[y];
if(rank[x]==rank[y]) ++rank[x];
}
--count_group;
}
bool is_same_group(int x,int y){
return find(x)==find(y);
}
int group_size(int x){
return gs[find(x)];
};
};
struct edge{
int from,to,cost;
bool operator<(const edge& other)const{
return cost<other.cost;
}
};
void solve(){
int n,m;
cin >> n >> m;
vector<edge> edges;
vector<unordered_map<int,int>> cost(n);
rep(i,0,m){
int a,b,c;
cin >> a >> b >> c;
--a;
--b;
edges.push_back(edge({a,b,c}));
}
sort(edges.begin(),edges.end());
int q;
cin >> q;
if(int64_t(m)*q>10000000) return;
rep(i,0,q){
int s,t;
cin >> s >> t;
--s;
--t;
union_find uf(n);
uf.unite(s,t);
int sum=0;
for(edge &edge:edges){
int a=edge.from,b=edge.to;
int x=uf.find(s),y=uf.find(t);
if(uf.is_same_group(a,b)) continue;
uf.unite(a,b);
sum+=edge.cost;
}
cout << sum << endl;
}
}
int main(){
std::cin.tie(0);
std::ios::sync_with_stdio(false);
cout.setf(ios::fixed);
cout.precision(10);
solve();
return 0;
}
Submission Info
Submission Time |
|
Task |
A - Graph |
User |
walkre |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2481 Byte |
Status |
WA |
Exec Time |
146 ms |
Memory |
6768 KB |
Judge Result
Set Name |
Sample |
subtask1 |
subtask2 |
All |
Score / Max Score |
0 / 0 |
0 / 200 |
0 / 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 |
WA |
3 ms |
256 KB |
subtask_1_10.txt |
WA |
72 ms |
3700 KB |
subtask_1_11.txt |
AC |
3 ms |
384 KB |
subtask_1_2.txt |
WA |
17 ms |
1404 KB |
subtask_1_3.txt |
WA |
145 ms |
6768 KB |
subtask_1_4.txt |
WA |
4 ms |
640 KB |
subtask_1_5.txt |
WA |
5 ms |
640 KB |
subtask_1_6.txt |
WA |
37 ms |
2168 KB |
subtask_1_7.txt |
WA |
143 ms |
6768 KB |
subtask_1_8.txt |
WA |
4 ms |
640 KB |
subtask_1_9.txt |
WA |
6 ms |
768 KB |
subtask_2_1.txt |
WA |
141 ms |
6768 KB |
subtask_2_2.txt |
WA |
142 ms |
6768 KB |
subtask_2_3.txt |
WA |
142 ms |
6768 KB |
subtask_2_4.txt |
WA |
141 ms |
6768 KB |
subtask_2_5.txt |
WA |
4 ms |
512 KB |
subtask_2_6.txt |
WA |
10 ms |
960 KB |
subtask_2_7.txt |
WA |
37 ms |
2168 KB |
subtask_2_8.txt |
WA |
141 ms |
6768 KB |
subtask_3_1.txt |
WA |
141 ms |
6768 KB |
subtask_3_2.txt |
WA |
141 ms |
6768 KB |
subtask_3_3.txt |
WA |
4 ms |
512 KB |
subtask_3_4.txt |
WA |
6 ms |
768 KB |
subtask_3_5.txt |
WA |
72 ms |
3700 KB |
subtask_3_6.txt |
WA |
111 ms |
6768 KB |
subtask_3_7.txt |
WA |
146 ms |
6768 KB |
subtask_3_8.txt |
WA |
141 ms |
6768 KB |