Submission #1476096
Source Code Expand
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
struct union_find{
VI par;
void init(int n){
par.resize(n);
REP(i,n) par[i] = i;
}
int find(int x){
if (par[x] == x) return x;
else return par[x] = find(par[x]);
}
bool same(int x, int y){
return find(x) == find(y);
}
void merge(int x, int y){
x = find(x);
y = find(y);
if (x == y) return;
par[x] = y;
}
};
struct edge{ int u, v, cost; };
VL em[4000], um[4000];
int ma[4000][4000];
bool comp(const edge &e1, const edge &e2){
return e1.cost < e2.cost;
}
ll kruskal(vector<edge> &es, int n){
sort(es.begin(), es.end(), comp);
union_find uf;
uf.init(n);
ll res = 0;
REP(i,es.size()){
edge e = es[i];
if (!uf.same(e.u, e.v)){
uf.merge(e.u, e.v);
res += e.cost;
em[e.u].push_back(e.v);
um[e.u].push_back(e.cost);
em[e.v].push_back(e.u);
um[e.v].push_back(e.cost);
}
}
return res;
}
void dfs(int now, int past, ll x, int s){
ma[s][now] = x;
REP(i,em[now].size()){
if (em[now][i] == past) continue;
dfs(em[now][i], now, max(x, um[now][i]), s);
}
}
int main(){
int n, m;
cin >> n >> m;
vector<edge> es;
while(m--){
edge eg;
scanf("%d %d %d", &eg.u, &eg.v, &eg.cost);
eg.u--;
eg.v--;
es.push_back(eg);
}
ll sum = kruskal(es, n);
REP(i,n) dfs(i, -1, 0, i);
int q;
cin >> q;
while (q--){
int s, t;
scanf("%d %d", &s, &t);
s--;
t--;
printf("%lld\n", sum - ma[s][t]);
}
return 0;
}
Submission Info
Submission Time |
|
Task |
A - Graph |
User |
TangentDay |
Language |
C++14 (GCC 5.4.1) |
Score |
700 |
Code Size |
2359 Byte |
Status |
AC |
Exec Time |
655 ms |
Memory |
70508 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:94:50: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &eg.u, &eg.v, &eg.cost);
^
./Main.cpp:108:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &s, &t);
^
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 |
384 KB |
sample_2.txt |
AC |
1 ms |
384 KB |
subtask_1_1.txt |
AC |
2 ms |
896 KB |
subtask_1_10.txt |
AC |
547 ms |
65520 KB |
subtask_1_11.txt |
AC |
1 ms |
384 KB |
subtask_1_2.txt |
AC |
487 ms |
63736 KB |
subtask_1_3.txt |
AC |
620 ms |
67948 KB |
subtask_1_4.txt |
AC |
422 ms |
63232 KB |
subtask_1_5.txt |
AC |
470 ms |
63360 KB |
subtask_1_6.txt |
AC |
511 ms |
64372 KB |
subtask_1_7.txt |
AC |
628 ms |
69228 KB |
subtask_1_8.txt |
AC |
428 ms |
63232 KB |
subtask_1_9.txt |
AC |
479 ms |
63304 KB |
subtask_2_1.txt |
AC |
621 ms |
68076 KB |
subtask_2_2.txt |
AC |
616 ms |
68588 KB |
subtask_2_3.txt |
AC |
626 ms |
68716 KB |
subtask_2_4.txt |
AC |
630 ms |
68972 KB |
subtask_2_5.txt |
AC |
414 ms |
63360 KB |
subtask_2_6.txt |
AC |
489 ms |
63484 KB |
subtask_2_7.txt |
AC |
514 ms |
64500 KB |
subtask_2_8.txt |
AC |
617 ms |
69100 KB |
subtask_3_1.txt |
AC |
653 ms |
69228 KB |
subtask_3_2.txt |
AC |
655 ms |
70380 KB |
subtask_3_3.txt |
AC |
453 ms |
64640 KB |
subtask_3_4.txt |
AC |
515 ms |
64576 KB |
subtask_3_5.txt |
AC |
580 ms |
67184 KB |
subtask_3_6.txt |
AC |
613 ms |
68588 KB |
subtask_3_7.txt |
AC |
650 ms |
70508 KB |
subtask_3_8.txt |
AC |
651 ms |
70252 KB |