Submission #2700567
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 + h + 2, -1);
int ans = 0;
int a = w+1;
int b = h+1;
rep(i, w+h){
if(get<2>(edge[i]) == 0){
int ww = get<1>(edge[i]);
int u = find(ww, parent);
int v = find(ww+1, parent);
unite(u, v, parent);
ans += get<0>(edge[i]) * b;
a--;
}else{
int hh = get<1>(edge[i]);
int u = find(w+1 + hh, parent);
int v = find(w+1 + hh+1, parent);
unite(u, v, parent);
ans += get<0>(edge[i]) * a;
b--;
}
}
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
C - Gr-idian MST |
User |
amanuko |
Language |
C++14 (Clang 3.8.0) |
Score |
500 |
Code Size |
1671 Byte |
Status |
AC |
Exec Time |
230 ms |
Memory |
8176 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
500 / 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 |
AC |
229 ms |
7792 KB |
02.txt |
AC |
229 ms |
7532 KB |
03.txt |
AC |
229 ms |
7788 KB |
04.txt |
AC |
230 ms |
7792 KB |
05.txt |
AC |
229 ms |
8048 KB |
06.txt |
AC |
228 ms |
7792 KB |
07.txt |
AC |
228 ms |
8176 KB |
08.txt |
AC |
228 ms |
7920 KB |
09.txt |
AC |
228 ms |
8048 KB |
10.txt |
AC |
228 ms |
7148 KB |
11.txt |
AC |
223 ms |
7276 KB |
12.txt |
AC |
223 ms |
7404 KB |
13.txt |
AC |
213 ms |
8176 KB |
14.txt |
AC |
226 ms |
8176 KB |
15.txt |
AC |
228 ms |
7788 KB |
16.txt |
AC |
114 ms |
4980 KB |
17.txt |
AC |
114 ms |
3956 KB |
18.txt |
AC |
114 ms |
4340 KB |
19.txt |
AC |
114 ms |
4980 KB |
20.txt |
AC |
110 ms |
7404 KB |
21.txt |
AC |
162 ms |
7792 KB |
22.txt |
AC |
164 ms |
7792 KB |
23.txt |
AC |
167 ms |
7020 KB |
24.txt |
AC |
220 ms |
7920 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 |