Submission #1000255
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define len(val) static_cast<ll>(val.size())
#define rep(i, n) for(ll i=0; i<(n); i++)
const ll MAXN = 4000;
const ll MAXM = 400000;
const ll INF = 1e18;
ll N, M;
struct UnionFind
{
std::vector<ll> data;
UnionFind(ll size) : data(size, -1){}
void initialize(void){
for(ll i=0; i<(ll)data.size(); i++) data[i] = i;
}
bool merge(ll x, ll y){
x = find(x); y = find(y);
if(x == y) return false;
else{ data[x] = y; return true; }
}
ll find(ll x){ //根っこを見つける関数
if(data[x] == x) return x;
else return data[x] = find(data[x]); //経路圧縮
}
bool isSame(ll x, ll y){
return find(x) == find(y);
}
};
struct edge{
ll u, v, cost;
};
bool comp(const edge& r, const edge& l){
return r.cost < l.cost;
}
edge es[MAXM];
ll mx[MAXN][MAXN];
bool visited[MAXN];
vector<P> G[MAXN];
void dfs(ll v, ll p, ll m = -1)
{
if(visited[v]) return;
mx[p][v] = m;
visited[v] = true;
for(auto a : G[v]){
dfs(a.first, p, max(m, a.second));
}
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
cin >> N >> M;
rep(i, M){
ll a, b, c;
cin >> a >> b >> c;
a--; b--;
es[i] = edge{a, b, c};
}
ll sum = 0;
{
sort(es, es+M, comp);
UnionFind uf(N);
uf.initialize();
ll cnt = 0;
rep(i, M){
edge& e = es[i];
if(!uf.isSame(e.u, e.v)){
uf.merge(e.u, e.v);
es[cnt] = edge{e.u, e.v, e.cost};
cnt++;
sum += e.cost;
G[e.u].push_back(make_pair(e.v, e.cost));
G[e.v].push_back(make_pair(e.u, e.cost));
}
}
}
for(int i=0; i<N; i++){
memset(visited, false, sizeof(visited));
dfs(i, i);
}
ll Q;
cin >> Q;
rep(q, Q){
ll s, t;
cin >> s >> t;
s--; t--;
cout << sum-mx[s][t] << endl;
}
}
Submission Info
Submission Time |
|
Task |
A - Graph |
User |
haraduka |
Language |
C++14 (GCC 5.4.1) |
Score |
700 |
Code Size |
2027 Byte |
Status |
AC |
Exec Time |
1161 ms |
Memory |
136192 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, 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 |
384 KB |
sample_2.txt |
AC |
3 ms |
384 KB |
subtask_1_1.txt |
AC |
4 ms |
896 KB |
subtask_1_10.txt |
AC |
617 ms |
130304 KB |
subtask_1_11.txt |
AC |
3 ms |
384 KB |
subtask_1_2.txt |
AC |
557 ms |
126592 KB |
subtask_1_3.txt |
AC |
701 ms |
134912 KB |
subtask_1_4.txt |
AC |
494 ms |
125696 KB |
subtask_1_5.txt |
AC |
543 ms |
125696 KB |
subtask_1_6.txt |
AC |
579 ms |
128000 KB |
subtask_1_7.txt |
AC |
696 ms |
134912 KB |
subtask_1_8.txt |
AC |
495 ms |
125696 KB |
subtask_1_9.txt |
AC |
553 ms |
125824 KB |
subtask_2_1.txt |
AC |
708 ms |
135040 KB |
subtask_2_2.txt |
AC |
701 ms |
135040 KB |
subtask_2_3.txt |
AC |
703 ms |
135040 KB |
subtask_2_4.txt |
AC |
707 ms |
135040 KB |
subtask_2_5.txt |
AC |
503 ms |
125696 KB |
subtask_2_6.txt |
AC |
573 ms |
126080 KB |
subtask_2_7.txt |
AC |
596 ms |
128000 KB |
subtask_2_8.txt |
AC |
703 ms |
135040 KB |
subtask_3_1.txt |
AC |
1135 ms |
136192 KB |
subtask_3_2.txt |
AC |
1161 ms |
136192 KB |
subtask_3_3.txt |
AC |
951 ms |
127104 KB |
subtask_3_4.txt |
AC |
1006 ms |
127104 KB |
subtask_3_5.txt |
AC |
1077 ms |
131456 KB |
subtask_3_6.txt |
AC |
1098 ms |
133760 KB |
subtask_3_7.txt |
AC |
1140 ms |
136192 KB |
subtask_3_8.txt |
AC |
1140 ms |
136192 KB |