1265 - Tour Belt

All about problems in Volume 12. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
aybek
New poster
Posts: 19
Joined: Fri Jul 19, 2013 10:25 am
Contact:

Re: 1265 - Tour Belt

Post by aybek » Fri Feb 06, 2015 10:48 am

I can't even suggest any solution :( . Any ideas?

aybek
New poster
Posts: 19
Joined: Fri Jul 19, 2013 10:25 am
Contact:

Re: 1265 - Tour Belt

Post by aybek » Fri Feb 06, 2015 8:18 pm

Help, I'm getting WA.
My solution's strategy is this: group edges with same weights.
After that, add heaviest edges. Count sizes of newly formed connected components.
Do the same for all edge groups from heaviest to lightest.
For test cases in the statement I got the same output, but my solution is not passing
all system tests.

Code: Select all

#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <cmath>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstring>
#include <climits>
#include <iomanip>
#include <iostream>
#include <algorithm>

#define INF INT_MAX-1
#define SQR(x) ((x)*(x))

using namespace std;

#define vertex_sz_MAX	5001
#define edge_w_MAX		100001

/* ufds */
namespace {
	int parent[vertex_sz_MAX];
	int size[vertex_sz_MAX];

	void init_set() {
		for (int i = 0; i < vertex_sz_MAX; ++i) {
			parent[i] = i;
			size[i] = 1;
		}
	}
	int find_set(int x) {
		return x == parent[x] ? x : parent[x] = find_set(parent[x]);
	}
	/* keeps track about newly formed components */
	void join_set(int x, int y, set<int> & new_comp) {
		x = find_set(x);
		y = find_set(y);

		if (x == y)
			return;

		if (size[x] > size[y]) {
			parent[y] = x;
			size[x] += size[y]; new_comp.insert(x);
			size[y] = 0; new_comp.erase(y);
		} else {
			parent[x] = y;
			size[y] += size[x]; new_comp.insert(y);
			size[x] = 0; new_comp.erase(x);
		}
	}
}

int vertex_sz, edges_sz, w_max;
list<pair<int, int> > edges[ edge_w_MAX ];

int solve() {
	init_set();

	set<int> new_comp;
	int count = 0;
	for (int w = w_max; w >= 1; --w) {
		new_comp.clear();

		/* add edges with same weights */
		for (list<pair<int, int> >::iterator it = edges[w].begin(); it != edges[w].end(); ++it) {
			join_set(it->first, it->second, new_comp);
		}

		for (set<int>::iterator it = new_comp.begin(); it != new_comp.end(); ++it) {
			count += size[*it];
		}
	}

	return count;
}

int main() {
	int test_n, x, y, w;
	cin >> test_n;

	while (test_n--) {
		/* prepare stage */
		w_max = 0;
		for (int i = 0; i < edge_w_MAX; ++i)
			edges[i].clear();

		/* input stage */
		cin >> vertex_sz >> edges_sz;
		while (edges_sz--) {
			cin >> x >> y >> w;
			w_max = max(w, w_max);
			edges[w].push_back(make_pair(x, y));
		}

		/* solve and output */
		cout << solve() << endl;
	}

	return 0;
}

aybek
New poster
Posts: 19
Joined: Fri Jul 19, 2013 10:25 am
Contact:

Re: 1265 - Tour Belt

Post by aybek » Fri Feb 06, 2015 8:30 pm

For this test case

Code: Select all

1
4 6
1 4 1
1 2 2
1 3 3
2 4 4
3 4 5
2 3 6
Solution's out is:

Code: Select all

9

fabikw
New poster
Posts: 3
Joined: Tue Oct 28, 2014 1:59 am

Re: 1265 - Tour Belt

Post by fabikw » Fri Aug 12, 2016 11:12 pm

My strategy is the following:
  • Sort edges in decreasing order
  • For each edge that connects two different components, check if each component is a candidate (this edge less than min edge in the component and size > 1), if so, add its size. Join the components.
  • Update the min size of the new component as the minimum of all inside edges (only need to check edges that join the two old components).
  • Finally add n

Post Reply

Return to “Volume 12 (1200-1299)”