Submission #996578
Source Code Expand
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
using namespace std;
typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define Fst first
#define Snd second
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)
#define repv(t,it,v) for(vector<t>::iterator it = v.begin() ; it != v.end() ; ++it)
const int UF_MAX = 1000000;
class UF{
int x[UF_MAX];
public:
UF(){
for(int i = 0 ; i < UF_MAX ; ++i) x[i] = -1;
}
int boss(int a){
int s = a;
while(x[s] > -1) s = x[s];
if(s != a) x[a] = s;
return s;
}
void uni(int a , int b){
int s = boss(a);
int t = boss(b);
if(s != t){
if(x[s] < x[t]){
x[s] += x[t];
x[t] = s;
} else {
x[t] += x[s];
x[s] = t;
}
}
}
bool find(int a , int b){
return boss(a) == boss(b);
}
int count(int a){
int b = 0;
for(int i = 0 ; i < a ; ++i) if(x[i] < 0) ++b;
return b;
}
} uf;
int N,M,Q;
vector<P2> V[4004];
vector<P3> E;
int d[4004];
int p[4004];
int q[4004];
void dfs(int a){
repv(P2,it,V[a]){
if(d[(*it).second] < 0){
d[(*it).second] = d[a] + 1;
p[(*it).second] = a;
q[(*it).second] = (*it).first;
dfs((*it).second);
}
}
}
int main(){
scanf("%d%d" , &N , &M);
repp(i,0,M){
int a,b,c;
scanf("%d%d%d" , &a , &b , &c);
E.PB(M3P(c,a,b));
}
sort(E.begin(),E.end());
int w = 0;
repp(i,0,M){
int x = E[i].first.second;
int y = E[i].second;
if(!uf.find(x,y)){
uf.uni(x,y);
V[x].PB(MP(E[i].first.first,y));
V[y].PB(MP(E[i].first.first,x));
w += E[i].first.first;
}
}
fill(d,d+N+1,-1);
fill(p,p+N+1,-1);
fill(q,q+N+1,0);
d[1] = 0;
dfs(1);
scanf("%d" , &Q);
repp(i,0,Q){
int s,t;
scanf("%d%d" , &s , &t);
int ans = 0;
while(s != t){
if(d[s] > d[t]){
ans = max(ans , q[s]);
s = p[s];
} else {
ans = max(ans , q[t]);
t = p[t];
}
}
printf("%d\n" , w - ans);
}
return 0;
}
Submission Info
Submission Time |
|
Task |
A - Graph |
User |
PIandS |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2409 Byte |
Status |
WA |
Exec Time |
194 ms |
Memory |
10608 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:86:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d" , &N , &M);
^
./Main.cpp:89:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d" , &a , &b , &c);
^
./Main.cpp:109:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d" , &Q);
^
./Main.cpp:112:26: 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 |
0 / 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 |
6 ms |
4224 KB |
sample_2.txt |
AC |
6 ms |
4224 KB |
subtask_1_1.txt |
WA |
7 ms |
4224 KB |
subtask_1_10.txt |
WA |
79 ms |
7412 KB |
subtask_1_11.txt |
AC |
6 ms |
4224 KB |
subtask_1_2.txt |
WA |
21 ms |
5244 KB |
subtask_1_3.txt |
WA |
153 ms |
10480 KB |
subtask_1_4.txt |
WA |
8 ms |
4480 KB |
subtask_1_5.txt |
WA |
9 ms |
4480 KB |
subtask_1_6.txt |
WA |
43 ms |
5880 KB |
subtask_1_7.txt |
WA |
152 ms |
10480 KB |
subtask_1_8.txt |
WA |
9 ms |
4480 KB |
subtask_1_9.txt |
WA |
11 ms |
4544 KB |
subtask_2_1.txt |
WA |
154 ms |
10480 KB |
subtask_2_2.txt |
WA |
154 ms |
10480 KB |
subtask_2_3.txt |
WA |
154 ms |
10480 KB |
subtask_2_4.txt |
WA |
154 ms |
10608 KB |
subtask_2_5.txt |
WA |
10 ms |
4480 KB |
subtask_2_6.txt |
WA |
16 ms |
4800 KB |
subtask_2_7.txt |
WA |
44 ms |
6008 KB |
subtask_2_8.txt |
WA |
154 ms |
10480 KB |
subtask_3_1.txt |
WA |
193 ms |
10480 KB |
subtask_3_2.txt |
WA |
193 ms |
10480 KB |
subtask_3_3.txt |
WA |
42 ms |
5632 KB |
subtask_3_4.txt |
WA |
49 ms |
5696 KB |
subtask_3_5.txt |
WA |
120 ms |
7792 KB |
subtask_3_6.txt |
WA |
160 ms |
10480 KB |
subtask_3_7.txt |
WA |
194 ms |
10480 KB |
subtask_3_8.txt |
WA |
193 ms |
10480 KB |