Submission #1151768
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, ll> P; vector< vector<P> > G; struct Union_Find { //各要素が属する集合の代表(根)を管理する //もし、要素xが根であればdata[x]は負の値を取り、-data[x]はxが属する集合の大きさに等しい vector<int> data; Union_Find(int size) : data(size, -1) {} bool Union(int x, int y) { x = Find(x); y = Find(y); bool is_union = (x != y); if (is_union) { if (data[x] > data[y]) swap(x, y); data[x] += data[y]; data[y] = x; } return is_union; } int Find(int x) { if (data[x] < 0) { //要素xが根である return x; } else { data[x] = Find(data[x]); //data[x]がxの属する集合の根でない場合、根になるよう更新される return data[x]; } } bool same(int x, int y) { return Find(x) == Find(y); } int size(int x) { return -data[Find(x)]; } }; struct Edge { int u, v; ll cost; bool operator<(const Edge& e) const { return cost < e.cost; } }; struct Graph { int n; //頂点数 vector<Edge> es; //辺集合 ll kruskal() { sort(es.begin(), es.end()); Union_Find uf(n); ll min_cost = 0; for(int i = 0; i < (int)es.size(); i++) { Edge e = es[i]; if (!uf.same(e.u, e.v)) { min_cost += e.cost; uf.Union(e.u, e.v); G[e.u].emplace_back(e.v, e.cost); G[e.v].emplace_back(e.u, e.cost); } } return min_cost; } }; Graph input() { Graph g; int m; cin >> g.n >> m; g.es = vector<Edge>(m); for(int i = 0; i < m; i++) { cin >> g.es[i].u >> g.es[i].v >> g.es[i].cost; g.es[i].u--; g.es[i].v--; } return g; } void dfs(int cur, int par, vector<ll>& d) { for (P nex : G[cur]) { if (nex.first == par) continue; d[nex.first] = max(d[cur], nex.second); dfs(nex.first, cur, d); } } int main() { cin.tie(0); ios::sync_with_stdio(false); Graph g = input(); G.resize(g.n); ll sum = g.kruskal(); vector< vector<ll> > maxc(g.n, vector<ll>(g.n, 0)); for (int i = 0; i < g.n; i++) { dfs(i, -1, maxc[i]); } int q; cin >> q; for (int i = 0; i < q; i++) { int s, t; cin >> s >> t; s--; t--; cout << sum - maxc[s][t] << endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - Graph |
User | fine |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 2728 Byte |
Status | AC |
Exec Time | 779 ms |
Memory | 133248 KB |
Judge Result
Set Name | Sample | subtask1 | subtask2 | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 200 / 200 | 300 / 300 | 200 / 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, 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 | 1 ms | 256 KB |
sample_2.txt | AC | 1 ms | 256 KB |
subtask_1_1.txt | AC | 2 ms | 384 KB |
subtask_1_10.txt | AC | 531 ms | 128896 KB |
subtask_1_11.txt | AC | 1 ms | 256 KB |
subtask_1_2.txt | AC | 480 ms | 126336 KB |
subtask_1_3.txt | AC | 597 ms | 131968 KB |
subtask_1_4.txt | AC | 445 ms | 125824 KB |
subtask_1_5.txt | AC | 472 ms | 125824 KB |
subtask_1_6.txt | AC | 502 ms | 127360 KB |
subtask_1_7.txt | AC | 616 ms | 131968 KB |
subtask_1_8.txt | AC | 439 ms | 125824 KB |
subtask_1_9.txt | AC | 479 ms | 125952 KB |
subtask_2_1.txt | AC | 604 ms | 132096 KB |
subtask_2_2.txt | AC | 603 ms | 132096 KB |
subtask_2_3.txt | AC | 616 ms | 132096 KB |
subtask_2_4.txt | AC | 605 ms | 132096 KB |
subtask_2_5.txt | AC | 441 ms | 125824 KB |
subtask_2_6.txt | AC | 484 ms | 126080 KB |
subtask_2_7.txt | AC | 510 ms | 127360 KB |
subtask_2_8.txt | AC | 610 ms | 132096 KB |
subtask_3_1.txt | AC | 776 ms | 133248 KB |
subtask_3_2.txt | AC | 775 ms | 133248 KB |
subtask_3_3.txt | AC | 623 ms | 127232 KB |
subtask_3_4.txt | AC | 661 ms | 127232 KB |
subtask_3_5.txt | AC | 722 ms | 130048 KB |
subtask_3_6.txt | AC | 748 ms | 131584 KB |
subtask_3_7.txt | AC | 777 ms | 133248 KB |
subtask_3_8.txt | AC | 779 ms | 133248 KB |