Submission #2700518
Source Code Expand
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <algorithm>
#include <utility>
#include <iomanip>
#define int long long int
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef pair<int, int> P;
const int INF = 1e15;
const int MOD = 1e9+7;
int find(int v, vector<int>& p){
if(p[v] == -1){
return v;
}
p[v] = find(p[v], p);
return p[v];
}
void unite(int u, int v, vector<int>& p){
int u_root = find(u, p);
int v_root = find(v, p);
if(u_root == v_root){
return;
}
p[u_root] = v_root;
}
signed main(){
int w, h;
cin >> w >> h;
vector<tuple<int, int, int>> edge;
rep(i, w){
int p;
cin >> p;
edge.emplace_back(p, i, 0);
}
rep(i, h){
int q;
cin >> q;
edge.emplace_back(q, i, 1);
}
sort(edge.begin(), edge.end());
vector<int> parent((w+1) * (h+1), -1);
int ans = 0;
rep(i, w+h){
if(get<2>(edge[i]) == 0){
int ww = get<1>(edge[i]);
rep(j, h+1){
int u = find((w+1)*j+ww, parent);
int v = find((w+1)*j+ww+1, parent);
if(u == v){
continue;
}
unite(u, v, parent);
ans += get<0>(edge[i]);
}
}else{
int hh = get<1>(edge[i]);
rep(j, w+1){
int u = find((w+1)*hh+j, parent);
int v = find((w+1)*(hh+1)+j, parent);
if(u == v){
continue;
}
unite(u, v, parent);
ans += get<0>(edge[i]);
}
}
}
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
C - Gr-idian MST |
User |
amanuko |
Language |
C++14 (Clang 3.8.0) |
Score |
0 |
Code Size |
1885 Byte |
Status |
RE |
Exec Time |
318 ms |
Memory |
8560 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 500 |
Status |
|
|
Set Name |
Test Cases |
Sample |
s1.txt, s2.txt |
All |
01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, s1.txt, s2.txt |
Case Name |
Status |
Exec Time |
Memory |
01.txt |
RE |
318 ms |
7280 KB |
02.txt |
RE |
317 ms |
8560 KB |
03.txt |
RE |
317 ms |
6896 KB |
04.txt |
RE |
318 ms |
7152 KB |
05.txt |
RE |
318 ms |
8560 KB |
06.txt |
RE |
317 ms |
8432 KB |
07.txt |
RE |
318 ms |
8432 KB |
08.txt |
RE |
317 ms |
6640 KB |
09.txt |
RE |
317 ms |
6896 KB |
10.txt |
RE |
317 ms |
8304 KB |
11.txt |
RE |
315 ms |
7408 KB |
12.txt |
RE |
313 ms |
7920 KB |
13.txt |
RE |
305 ms |
6640 KB |
14.txt |
RE |
318 ms |
8048 KB |
15.txt |
RE |
317 ms |
7792 KB |
16.txt |
AC |
119 ms |
4980 KB |
17.txt |
AC |
119 ms |
4336 KB |
18.txt |
AC |
123 ms |
5488 KB |
19.txt |
AC |
124 ms |
5104 KB |
20.txt |
RE |
202 ms |
6768 KB |
21.txt |
RE |
254 ms |
6896 KB |
22.txt |
RE |
258 ms |
7408 KB |
23.txt |
RE |
260 ms |
7024 KB |
24.txt |
RE |
316 ms |
8560 KB |
25.txt |
AC |
1 ms |
256 KB |
26.txt |
AC |
1 ms |
256 KB |
27.txt |
AC |
1 ms |
256 KB |
28.txt |
AC |
1 ms |
256 KB |
s1.txt |
AC |
1 ms |
256 KB |
s2.txt |
AC |
1 ms |
256 KB |