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
Task G - Zigzag MST
User vjudge5
Language C++14 (Clang 3.8.0)
Score 1300
Code Size 1464 Byte
Status
Exec Time 76 ms
Memory 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