Submission #57960

#	Time	Username	Problem	Language	Result	Execution time	Memory
57960		fredbr	ICC (CEOI16_icc)	C++17	18 / 100	588 ms	832 KiB

icc

#include <bits/stdc++.h>
#include "icc.h"

using namespace std;

const int maxn = 110;

int roads = 0;

struct Dsu
{
	int pai[maxn], w[maxn];

	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 (w[x] < w[y]) swap(x, y);
		pai[y] = x;
		w[x] += y;
	}

	void reset(int x)
	{
		for(int i = 1; i <= x; i++)
			pai[i] = i, w[i] = 1;
	}
};

Dsu dsu;

bool find(int n, int x)
{
	vector<int> v;
	vector<int> vx = {x};
	for (int i = x+1; i <= n; i++)
		if (dsu.find(i) != dsu.find(x))
			v.push_back(i);

	if (v.size() == 0) return false;	
	return query(1, v.size(), vx.data(), v.data());
}

int qrs = 0;

void solve(int n, int x)
{
	for (int i = x+1; i <= n; i++) {

		if (dsu.find(i) == dsu.find(x))
			continue;

		vector<int> vx = {x};
		vector<int> v = {i};

		qrs++;

		if (query(1, 1, vx.data(), v.data())) {

			// if (roads == n-2)
				// cout << qrs << "\n";
			setRoad(x, i);
			roads++;
			dsu.join(x, i);
			break;
		}
	}
}

void run(int n)
{	
	dsu.reset(n);
	while (roads < n-1) {

		int root;
		for (int i = 1; i < n; i++) {
			if (find(n, i)) {
				root = i;
				break;
			}
		}
		solve(n, root);
	}
}

Compilation message (stderr)

icc.cpp: In function 'void run(int)':
icc.cpp:87:8: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   solve(n, root);
   ~~~~~^~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 21
• Subtask 5: 0 / 29
• Subtask 6: 0 / 10