Submission #993890
Source Code Expand
#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <set>
#include <bitset>
#include <map>
#include <deque>
#include <string>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#define pb push_back
#define pbk pop_back
#define mp make_pair
#define fs first
#define sc second
#define all(x) (x).begin(), (x).end()
#define foreach(i, a) for (__typeof((a).begin()) i = (a).begin(); i != (a).end(); ++i)
#define len(a) ((int) (a).size())
#ifdef CUTEBMAING
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define eprintf(...) 42
#endif
using namespace std;
typedef long long int64;
typedef long double ld;
typedef unsigned long long lint;
const int inf = (1 << 30) - 1;
const int64 linf = (1ll << 62) - 1;
const int N = 1e6 + 100;
int n, q;
int a[N], b[N], c[N];
int parent[N];
inline int findSet(int v) {
if (parent[v] != v) {
return parent[v] = findSet(parent[v]);
}
return v;
}
int main() {
#ifdef XCODE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
cin >> n >> q;
for (int i = 0; i < q; i++) {
scanf("%d%d%d", &a[i], &b[i], &c[i]);
}
for (int i = 0; i < n; i++) {
parent[i] = i;
}
set<tuple<int, int, int, int>> st;
for (int i = 0; i < q; i++) {
st.insert(make_tuple(c[i], a[i], b[i], 0));
}
int64 ans = 0;
while (len(st) > 0) {
int c, u, v, cnt; tie(c, u, v, cnt) = *st.begin();
st.erase(st.begin());
if (findSet(u) == findSet(v)) {
if (cnt >= 2) {
continue;
} else {
st.insert(make_tuple(c + 1, v, (u + 1) % n, cnt + 1));
continue;
}
}
ans += c;
parent[findSet(u)] = findSet(v);
st.insert(make_tuple(c + 1, v, (u + 1) % n, 0));
}
for (int i = 0; i < n; i++) {
assert(findSet(0) == findSet(i));
}
cout << ans << endl;
return 0;
}
Submission Info
Submission Time
2016-11-26 14:21:28+0900
Task
G - Zigzag MST
User
darinflar
Language
C++14 (GCC 5.4.1)
Score
1300
Code Size
2166 Byte
Status
AC
Exec Time
487 ms
Memory
17792 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:65:45: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &a[i], &b[i], &c[i]);
^
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
3 ms
256 KB
01-02.txt
AC
166 ms
15104 KB
01-03.txt
AC
214 ms
16000 KB
01-04.txt
AC
19 ms
2432 KB
01-05.txt
AC
23 ms
1664 KB
01-06.txt
AC
24 ms
1408 KB
01-07.txt
AC
25 ms
1152 KB
01-08.txt
AC
30 ms
1152 KB
01-09.txt
AC
55 ms
1792 KB
01-10.txt
AC
152 ms
8448 KB
01-11.txt
AC
228 ms
15488 KB
01-12.txt
AC
258 ms
15872 KB
01-13.txt
AC
265 ms
15872 KB
01-14.txt
AC
267 ms
15872 KB
01-15.txt
AC
259 ms
15872 KB
01-16.txt
AC
266 ms
15872 KB
01-17.txt
AC
265 ms
15872 KB
01-18.txt
AC
82 ms
5248 KB
01-19.txt
AC
27 ms
1152 KB
01-20.txt
AC
70 ms
1152 KB
01-21.txt
AC
188 ms
5376 KB
01-22.txt
AC
487 ms
15872 KB
01-23.txt
AC
476 ms
15872 KB
01-24.txt
AC
34 ms
3840 KB
01-25.txt
AC
178 ms
17792 KB
01-26.txt
AC
29 ms
2944 KB
01-27.txt
AC
70 ms
1792 KB
01-28.txt
AC
248 ms
10240 KB
01-29.txt
AC
364 ms
15488 KB
01-30.txt
AC
405 ms
15872 KB
sample-01.txt
AC
3 ms
256 KB
sample-02.txt
AC
3 ms
256 KB
sample-03.txt
AC
3 ms
256 KB