Submission #1986390
Source Code Expand
#include <bits/stdc++.h>
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))
using namespace std;
template<class T>bool chmax(T &a, const T &b) { return (a < b) ? (a = b, 1) : 0;}
template<class T>bool chmin(T &a, const T &b) { return (b < a) ? (a = b, 1) : 0;}
using ll = long long;
using R = long double;
const R EPS = 1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r) {return (r > EPS) - (r < -EPS);}
inline R sq(R x) {return sqrt(max(x, 0.0L));}
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
// Problem Specific Parameter:
// Description: 素集合を管理するデータ構造
// TimeComplexity: 初期化$\mathcal{O}(n)$ 更新$\mathcal{O}(\log n)$
// Verifyed: AOJ DSL_1_A
struct Union_find {
Union_find(int n) {par.resize(n), iota(_all(par), 0);}
int find(int x) {return (par[x] == x) ? x : par[x] = find(par[x]);}
void unite(int a, int b) {a = find(a), b = find(b); par[a] = b;}
bool same(int a, int b) {return find(a) == find(b);}
vector<int> par;
};
using edge = struct {int to; ll cost;};
using G = vector<vector<edge>>;
G graph;
const int limit = 4010;
ll dist[limit][limit];
void dfs(int v, int p, int s, ll c) {
chmax(dist[s][v], c);
for (auto &e : graph[v]) {
if (e.to == p) continue;
dfs(e.to, v, s, max(c, e.cost));
}
}
int main(void) {
int n, m;
cin >> n >> m;
using edge = tuple < ll, ll, ll>;
vector<edge> edges;
rep(i, m) {
ll a, b, c;
cin >> a >> b >> c;
a--, b--;
edges.push_back(edge(c, a, b));
}
sort(begin(edges), end(edges));
Union_find uf(n);
ll res = 0LL;
graph = G(n);
for (auto &e : edges) {
ll c, a, b;
tie(c, a, b) = e;
if (uf.same(a, b)) continue;
uf.unite(a, b);
res += c;
graph[a].push_back({b, c});
graph[b].push_back({a, c});
}
rep(v, n) dfs(v, -1, v, 0LL);
int q;
cin >> q;
rep(loop, q) {
int s, t;
cin >> s >> t;
s--, t--;
cout << res - dist[s][t] << endl;
}
return 0;
}
Submission Info
Submission Time
2018-01-17 02:32:14+0900
Task
A - Graph
User
Hec
Language
C++14 (GCC 5.4.1)
Score
700
Code Size
2668 Byte
Status
AC
Exec Time
1022 ms
Memory
138216 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:88:28: warning: narrowing conversion of ‘b’ from ‘ll {aka long long int}’ to ‘int’ inside { } [-Wnarrowing]
graph[a].push_back({b, c});
^
./Main.cpp:89:28: warning: narrowing conversion of ‘a’ from ‘ll {aka long long int}’ to ‘int’ inside { } [-Wnarrowing]
graph[b].push_back({a, c});
^
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
3 ms
2688 KB
subtask_1_10.txt
AC
615 ms
132076 KB
subtask_1_11.txt
AC
1 ms
256 KB
subtask_1_2.txt
AC
463 ms
126836 KB
subtask_1_3.txt
AC
808 ms
136808 KB
subtask_1_4.txt
AC
380 ms
125952 KB
subtask_1_5.txt
AC
429 ms
126016 KB
subtask_1_6.txt
AC
518 ms
128368 KB
subtask_1_7.txt
AC
808 ms
136168 KB
subtask_1_8.txt
AC
369 ms
125952 KB
subtask_1_9.txt
AC
451 ms
126076 KB
subtask_2_1.txt
AC
815 ms
135784 KB
subtask_2_2.txt
AC
819 ms
135528 KB
subtask_2_3.txt
AC
806 ms
136936 KB
subtask_2_4.txt
AC
815 ms
137320 KB
subtask_2_5.txt
AC
376 ms
125952 KB
subtask_2_6.txt
AC
459 ms
126328 KB
subtask_2_7.txt
AC
528 ms
128240 KB
subtask_2_8.txt
AC
812 ms
136168 KB
subtask_3_1.txt
AC
1013 ms
138216 KB
subtask_3_2.txt
AC
1022 ms
136680 KB
subtask_3_3.txt
AC
603 ms
127360 KB
subtask_3_4.txt
AC
664 ms
127356 KB
subtask_3_5.txt
AC
828 ms
132716 KB
subtask_3_6.txt
AC
929 ms
135784 KB
subtask_3_7.txt
AC
1016 ms
136808 KB
subtask_3_8.txt
AC
1012 ms
137704 KB