oj.uz

Submission #373438

# Submission time Handle Problem Language Result Execution time Memory
373438 2021-03-04T15:23:19 Z luciocf timeismoney (balkan11_timeismoney) C++14
40 / 100
 6 ms 620 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;

struct Edge
{
	int u, v, w;
} edge[maxn];

struct DSU
{
	int pai[maxn], peso[maxn];

	void init(int n)
	{
		for (int i = 1; i <= n; i++)
			pai[i] = i, peso[i] = 1;
	}

	int Find(int x)
	{
		if (pai[x] == x) return x;
		return pai[x] = Find(pai[x]);
	}

	void Join(int x, int y)
	{
		x = Find(x), y = Find(y);
		if (x == y) return;

		if (peso[x] < peso[y]) swap(x, y);

		pai[y] = x, peso[x] += peso[y];
	}
} dsu;

bool comp(Edge a, Edge b)
{
	return a.w < b.w;
}

int main(void)
{
	int n, m;
	scanf("%d %d", &n, &m);

	for (int i = 1; i <= m; i++)
	{
		int u, v, w, w2;
		scanf("%d %d %d %d", &u, &v, &w, &w2);

		u++, v++;
		edge[i] = {u, v, w};
	}

	sort(edge+1, edge+m+1, comp);
	dsu.init(n);

	int ans = 0;
	vector<pair<int, int>> ans_edge;

	for (int i = 1; i <= m; i++)
	{
		if (dsu.Find(edge[i].u) != dsu.Find(edge[i].v))
		{
			dsu.Join(edge[i].u, edge[i].v);

			ans += edge[i].w;
			ans_edge.push_back({edge[i].u, edge[i].v});
		}
	}

	printf("%d %d\n", ans, ans);
	for (auto pp: ans_edge)
		printf("%d %d\n", pp.first-1, pp.second-1);
}

Compilation message

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
timeismoney.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |   scanf("%d %d %d %d", &u, &v, &w, &w2);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 6 ms 620 KB Output is correct
9 Incorrect 1 ms 364 KB Output isn't correct
10 Incorrect 1 ms 364 KB Output isn't correct
11 Incorrect 1 ms 364 KB Output isn't correct
12 Incorrect 1 ms 364 KB Output isn't correct
13 Incorrect 1 ms 364 KB Output isn't correct
14 Incorrect 1 ms 364 KB Output isn't correct
15 Incorrect 1 ms 364 KB Output isn't correct
16 Incorrect 1 ms 364 KB Output isn't correct
17 Incorrect 1 ms 364 KB Output isn't correct
18 Incorrect 2 ms 364 KB Output isn't correct
19 Incorrect 5 ms 620 KB Output isn't correct
20 Incorrect 6 ms 620 KB Output isn't correct