Submission #993696


Source Code Expand

#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <list>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <iostream>
#include <sstream>
using namespace std;

typedef long long i64;
const int inf = (int)1.05e9;


struct UnionFind {

	vector<int> par;

	void init(int size)
	{
		par.resize(size);
		for(int i = 0; i < size; ++i)
			par[i] = i;
	}

	int root(int x)
	{
		if(par[x] == x)
			return x;
		return par[x] = root(par[x]);
	}

	bool same(int a, int b)
	{
		return root(a) == root(b);
	}

	void unite(int a, int b)
	{
		a = root(a);
		b = root(b);
		par[a] = b;
	}
};


int main()
{
	int n, q;
	UnionFind uf;
	priority_queue<pair<i64,pair<int,int>>> pq;

	scanf("%d%d", &n, &q);
	uf.init(n);

	for(int i = 0; i < q; ++i) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		pq.push({-((i64)c), {a, b}});
		pq.push({-((i64)(c + 1)), {(a + 1) % n, b}});
	}

	i64 ans = 0;

	while(!pq.empty()) {

		auto candy = pq.top();
		pq.pop();
		i64 cost = -candy.first;
		int a = candy.second.first;
		int b = candy.second.second;

		if(uf.same(a, b))
			continue;
		uf.unite(a, b);
		//printf("%lld: %d-%d\n", cost, a, b);

		ans += cost;
		pq.push({-((i64)(cost + 2)), {(a + 1) % n, (b + 1) % n}});
	}

	printf("%lld\n", ans);

	return 0;
}

Submission Info

Submission Time
Task G - Zigzag MST
User wafrelka
Language C++14 (GCC 5.4.1)
Score 1300
Code Size 1417 Byte
Status AC
Exec Time 211 ms
Memory 9324 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:58:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &q);
                       ^
./Main.cpp:63:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &a, &b, &c);
                              ^

Judge Result

Set Name sample all
Score / Max Score 0 / 0 1300 / 1300
Status
AC × 3
AC × 33
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 131 ms 8556 KB
01-03.txt AC 164 ms 9324 KB
01-04.txt AC 9 ms 1664 KB
01-05.txt AC 11 ms 1280 KB
01-06.txt AC 13 ms 1280 KB
01-07.txt AC 14 ms 1152 KB
01-08.txt AC 23 ms 1152 KB
01-09.txt AC 38 ms 1660 KB
01-10.txt AC 111 ms 5232 KB
01-11.txt AC 163 ms 8940 KB
01-12.txt AC 188 ms 9324 KB
01-13.txt AC 189 ms 9324 KB
01-14.txt AC 188 ms 9324 KB
01-15.txt AC 189 ms 9324 KB
01-16.txt AC 189 ms 9324 KB
01-17.txt AC 189 ms 9324 KB
01-18.txt AC 109 ms 9324 KB
01-19.txt AC 12 ms 1152 KB
01-20.txt AC 32 ms 1152 KB
01-21.txt AC 88 ms 3188 KB
01-22.txt AC 209 ms 9324 KB
01-23.txt AC 211 ms 9324 KB
01-24.txt AC 15 ms 1660 KB
01-25.txt AC 139 ms 9324 KB
01-26.txt AC 9 ms 1024 KB
01-27.txt AC 32 ms 1660 KB
01-28.txt AC 129 ms 5232 KB
01-29.txt AC 176 ms 8940 KB
01-30.txt AC 195 ms 9324 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