Contest Duration: ~ (local time) (180 minutes)

Submission #6352815

Source Code Expand

Copy
```#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
inline int gi() {
register int data = 0, w = 1;
register char ch = 0;
while (!isdigit(ch) && ch != '-') ch = getchar();
if (ch == '-') w = -1, ch = getchar();
while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar();
return w * data;
}
const int MAX_N = 2e5 + 5;
const int INF = 2e9;
struct Edge { int u, v, w; } e[MAX_N << 1];
bool operator < (const Edge &l, const Edge &r) { return l.w < r.w; }
int N, cnt, Q, ds[MAX_N];
int pa[MAX_N];
int getf(int x) { return x == pa[x] ? x : pa[x] = getf(pa[x]); }
long long ans = 0;
int main () {
N = gi(), Q = gi();
for (int i = 1; i <= N; i++) ds[i] = INF;
while (Q--) {
int A = gi() + 1, B = gi() + 1, C = gi();
e[++cnt] = (Edge){A, B, C};
ds[A % N + 1] = min(ds[A % N + 1], C + 1);
ds[B % N + 1] = min(ds[B % N + 1], C + 2);
}
int pos = min_element(&ds[1], &ds[N + 1]) - ds;
for (int i = pos % N + 1, j = pos; i != pos; j = i, i = i % N + 1) ds[i] = min(ds[j] + 2, ds[i]);
for (int i = 2; i <= N; i++) e[++cnt] = (Edge){i - 1, i, ds[i]};
e[++cnt] = (Edge){N, 1, ds[1]};
sort(&e[1], &e[cnt + 1]);
for (int i = 1; i <= N; i++) pa[i] = i;
for (int i = 1; i <= cnt; i++) {
int u = getf(e[i].u), v = getf(e[i].v);
if (u == v) continue;
ans += e[i].w, pa[u] = v;
}
printf("%lld\n", ans);
return 0;
}
```

#### Submission Info

Submission Time 2019-07-12 22:58:15+0900 G - Zigzag MST vjudge5 C++14 (Clang 3.8.0) 1300 1464 Byte AC 76 ms 9600 KB

#### Compile Error

```./Main.cpp:9:5: warning: 'register' storage class specifier is deprecated and incompatible with C++1z [-Wdeprecated-register]
register int data = 0, w = 1;
^~~~~~~~~
./Main.cpp:9:5: warning: 'register' storage class specifier is deprecated and incompatible with C++1z [-Wdeprecated-register]
register int data = 0, w = 1;
^~~~~~~~~
./Main.cpp:10:5: warning: 'register' storage class specifier is deprecated and incompatible with C++1z [-Wdeprecated-register]
register char ch = 0;
^~~~~~~~~
3 warnings generated.
```

#### Judge Result

Set Name Score / Max Score Test Cases
sample 0 / 0 sample-01.txt, sample-02.txt, sample-03.txt
all 1300 / 1300 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, sample-01.txt, sample-02.txt, sample-03.txt
Case Name Status Exec Time Memory
01-01.txt 1 ms 2304 KB
01-02.txt 42 ms 6400 KB
01-03.txt 74 ms 6784 KB
01-04.txt 13 ms 8832 KB
01-05.txt 11 ms 7552 KB
01-06.txt 13 ms 8064 KB
01-07.txt 15 ms 6912 KB
01-08.txt 16 ms 6656 KB
01-09.txt 20 ms 6528 KB
01-10.txt 45 ms 6528 KB
01-11.txt 62 ms 6400 KB
01-12.txt 73 ms 6528 KB
01-13.txt 73 ms 6528 KB
01-14.txt 75 ms 6528 KB
01-15.txt 76 ms 6528 KB
01-16.txt 74 ms 6528 KB
01-17.txt 74 ms 6528 KB
01-18.txt 46 ms 9600 KB
01-19.txt 14 ms 6784 KB
01-20.txt 17 ms 6528 KB
01-21.txt 30 ms 6528 KB
01-22.txt 53 ms 6528 KB
01-23.txt 53 ms 6528 KB
01-24.txt 13 ms 9600 KB
01-25.txt 56 ms 9600 KB
01-26.txt 14 ms 9216 KB
01-27.txt 18 ms 8064 KB
01-28.txt 46 ms 8064 KB
01-29.txt 52 ms 7296 KB
01-30.txt 63 ms 8064 KB
sample-01.txt 1 ms 2304 KB
sample-02.txt 1 ms 2304 KB
sample-03.txt 1 ms 2304 KB