Submission #993258
Source Code Expand
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <random>
#include <vector>
#include <array>
#include <bitset>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <queue>
using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); }
int bsr(int x) { return 31 - __builtin_clz(x); }
struct UnionFind {
vector<int> ig;
vector<vector<int>> gi;
int gn;
UnionFind(int N) {
ig.resize(N); gi.resize(N);
for (int i = 0; i < N; i++) {
ig[i] = i; gi[i] = {i};
}
gn = N;
}
void merge(int a, int b) {
if (same(a, b)) return;
gn--;
int x = ig[a], y = ig[b];
if (gi[x].size() < gi[y].size()) swap(x, y);
for (int j: gi[y]) {
ig[j] = x;
}
gi[x].insert(gi[x].end(), gi[y].begin(), gi[y].end());
gi[y].clear();
}
bool same(int a, int b) {
return ig[a] == ig[b];
}
};
int main() {
ios::sync_with_stdio(0);
cout << setprecision(20);
int n, q;
cin >> n >> q;
using T = tuple<ll, int, int, bool>;
priority_queue<T, vector<T>, greater<T>> que;
for (int i = 0; i < q; i++) {
int a, b; ll c;
cin >> a >> b >> c;
que.push(T(c, a, b, false));
}
UnionFind uf(n);
ll ans = 0;
while (uf.gn > 1) {
if (que.size() == 0) break;
int a, b; ll c; bool f;
tie(c, a, b, f) = que.top(); que.pop();
// cout << a << " " << b << " " << c << endl;
if (!uf.same(a, b)) {
uf.merge(a, b);
ans += c;
que.push(T(c+1, b, (a+1)%n, false));
} else {
if (!f) {
que.push(T(c+1, b, (a+1)%n, true));
}
}
}
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
G - Zigzag MST |
User |
yosupo |
Language |
C++14 (GCC 5.4.1) |
Score |
1300 |
Code Size |
2013 Byte |
Status |
AC |
Exec Time |
247 ms |
Memory |
19436 KB |
Judge Result
Set Name |
sample |
all |
Score / Max Score |
0 / 0 |
1300 / 1300 |
Status |
|
|
Set Name |
Test Cases |
sample |
sample-01.txt, sample-02.txt, sample-03.txt |
all |
sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt |
Case Name |
Status |
Exec Time |
Memory |
01-01.txt |
AC |
2 ms |
256 KB |
01-02.txt |
AC |
67 ms |
6512 KB |
01-03.txt |
AC |
131 ms |
18668 KB |
01-04.txt |
AC |
30 ms |
13180 KB |
01-05.txt |
AC |
34 ms |
13180 KB |
01-06.txt |
AC |
38 ms |
13180 KB |
01-07.txt |
AC |
42 ms |
14012 KB |
01-08.txt |
AC |
48 ms |
13860 KB |
01-09.txt |
AC |
70 ms |
14232 KB |
01-10.txt |
AC |
115 ms |
16496 KB |
01-11.txt |
AC |
116 ms |
12140 KB |
01-12.txt |
AC |
161 ms |
19180 KB |
01-13.txt |
AC |
160 ms |
18668 KB |
01-14.txt |
AC |
161 ms |
19436 KB |
01-15.txt |
AC |
161 ms |
18924 KB |
01-16.txt |
AC |
162 ms |
18924 KB |
01-17.txt |
AC |
162 ms |
19308 KB |
01-18.txt |
AC |
136 ms |
18412 KB |
01-19.txt |
AC |
38 ms |
14096 KB |
01-20.txt |
AC |
76 ms |
14096 KB |
01-21.txt |
AC |
128 ms |
16116 KB |
01-22.txt |
AC |
243 ms |
19180 KB |
01-23.txt |
AC |
247 ms |
18668 KB |
01-24.txt |
AC |
41 ms |
13560 KB |
01-25.txt |
AC |
187 ms |
18540 KB |
01-26.txt |
AC |
36 ms |
13180 KB |
01-27.txt |
AC |
64 ms |
14348 KB |
01-28.txt |
AC |
157 ms |
17136 KB |
01-29.txt |
AC |
190 ms |
12780 KB |
01-30.txt |
AC |
221 ms |
18796 KB |
sample-01.txt |
AC |
3 ms |
256 KB |
sample-02.txt |
AC |
3 ms |
256 KB |
sample-03.txt |
AC |
2 ms |
256 KB |