Submission #2070887


Source Code Expand

#include <algorithm>
#include <cstdio>
struct edge
{
	int u, v, w; 
	edge(int _u = 0, int _v = 0, int _w = 0)
	{
		u = _u; 
		v = _v; 
		w = _w; 
	}
	inline bool operator <(const edge &a) const
	{
		return w < a.w; 
	}
} arr[400005]; 
int fa[400005], w[400005]; 
int getfa(int u)
{
	if (u == fa[u])
		return u; 
	return fa[u] = getfa(fa[u]); 
}
int main()
{
	// freopen("CF16-final-G.in", "r", stdin); 
	int n, m; 
	scanf("%d%d", &n, &m); 
	for (int i = 0; i < n; i++)
	{
		fa[i] = i; 
		w[i] = w[i + n] = 2e9; 
	}
	for (int i = 0; i < m; i++)
	{
		scanf("%d%d%d", &arr[i].u, &arr[i].v, &arr[i].w); 
		w[arr[i].u] = std::min(w[arr[i].u], arr[i].w + 1); 
		w[arr[i].v] = std::min(w[arr[i].v], arr[i].w + 2); 
	}
	for (int i = 1; i < n << 1; i++)
		w[i] = std::min(w[i - 1] + 2, w[i]); 
	for (int i = 0; i < n; i++)
		arr[m++] = edge(i, (i + 1) % n, std::min(w[i], w[i + n]));
	std::sort(arr, arr + m); 
	long long ans = 0; 
	for (int i = 0; i < m; i++)
	{
		int u = getfa(arr[i].u), v = getfa(arr[i].v); 
		if (u != v)
		{
			fa[u] = v; 
			ans += arr[i].w; 
		}
	}
	printf("%lld\n", ans);
	return 0; 
}

Submission Info

Submission Time
Task G - Zigzag MST
User diamond_duke
Language C++14 (GCC 5.4.1)
Score 1300
Code Size 1160 Byte
Status AC
Exec Time 91 ms
Memory 11136 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:28:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m); 
                       ^
./Main.cpp:36:51: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &arr[i].u, &arr[i].v, &arr[i].w); 
                                                   ^

Judge Result

Set Name sample all
Score / Max Score 0 / 0 1300 / 1300
Status
AC × 3
AC × 36
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, sample-01.txt, sample-02.txt, sample-03.txt
Case Name Status Exec Time Memory
01-01.txt AC 2 ms 5888 KB
01-02.txt AC 62 ms 5888 KB
01-03.txt AC 89 ms 8192 KB
01-04.txt AC 21 ms 10240 KB
01-05.txt AC 14 ms 9088 KB
01-06.txt AC 18 ms 9472 KB
01-07.txt AC 16 ms 8320 KB
01-08.txt AC 16 ms 8064 KB
01-09.txt AC 21 ms 8064 KB
01-10.txt AC 54 ms 7936 KB
01-11.txt AC 78 ms 7168 KB
01-12.txt AC 90 ms 7936 KB
01-13.txt AC 89 ms 7936 KB
01-14.txt AC 89 ms 7936 KB
01-15.txt AC 91 ms 7936 KB
01-16.txt AC 89 ms 7936 KB
01-17.txt AC 89 ms 7936 KB
01-18.txt AC 68 ms 11136 KB
01-19.txt AC 15 ms 8320 KB
01-20.txt AC 19 ms 7936 KB
01-21.txt AC 38 ms 7936 KB
01-22.txt AC 77 ms 7936 KB
01-23.txt AC 77 ms 7936 KB
01-24.txt AC 16 ms 11136 KB
01-25.txt AC 88 ms 11136 KB
01-26.txt AC 21 ms 10624 KB
01-27.txt AC 23 ms 9472 KB
01-28.txt AC 58 ms 9472 KB
01-29.txt AC 74 ms 8192 KB
01-30.txt AC 84 ms 9472 KB
sample-01.txt AC 2 ms 5888 KB
sample-02.txt AC 2 ms 5888 KB
sample-03.txt AC 2 ms 5888 KB