Submission #1026557
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; 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); int64_t sum=0; for(edge &edge:edges){ int a=edge.from,b=edge.to; 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 | 200 |
Code Size | 2396 Byte |
Status | WA |
Exec Time | 145 ms |
Memory | 6512 KB |
Judge Result
Set Name | Sample | subtask1 | subtask2 | All | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 200 / 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 | AC | 3 ms | 256 KB |
subtask_1_10.txt | AC | 72 ms | 3444 KB |
subtask_1_11.txt | AC | 3 ms | 256 KB |
subtask_1_2.txt | AC | 17 ms | 1148 KB |
subtask_1_3.txt | AC | 143 ms | 6512 KB |
subtask_1_4.txt | AC | 4 ms | 384 KB |
subtask_1_5.txt | AC | 4 ms | 384 KB |
subtask_1_6.txt | AC | 37 ms | 1912 KB |
subtask_1_7.txt | AC | 143 ms | 6512 KB |
subtask_1_8.txt | AC | 4 ms | 384 KB |
subtask_1_9.txt | AC | 6 ms | 640 KB |
subtask_2_1.txt | WA | 141 ms | 6512 KB |
subtask_2_2.txt | WA | 141 ms | 6512 KB |
subtask_2_3.txt | WA | 141 ms | 6512 KB |
subtask_2_4.txt | WA | 141 ms | 6512 KB |
subtask_2_5.txt | WA | 4 ms | 384 KB |
subtask_2_6.txt | WA | 9 ms | 832 KB |
subtask_2_7.txt | WA | 37 ms | 1912 KB |
subtask_2_8.txt | WA | 141 ms | 6512 KB |
subtask_3_1.txt | WA | 143 ms | 6512 KB |
subtask_3_2.txt | WA | 142 ms | 6512 KB |
subtask_3_3.txt | WA | 4 ms | 384 KB |
subtask_3_4.txt | WA | 6 ms | 512 KB |
subtask_3_5.txt | WA | 73 ms | 3444 KB |
subtask_3_6.txt | WA | 108 ms | 6512 KB |
subtask_3_7.txt | WA | 145 ms | 6512 KB |
subtask_3_8.txt | WA | 142 ms | 6512 KB |