oj.uz

Submission #57960

# Submission time Handle Problem Language Result Execution time Memory
57960 2018-07-16T14:40:08 Z fredbr ICC (CEOI16_icc) C++17
18 / 100
 588 ms 832 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 504 KB Ok! 210 queries used.
2 Correct 23 ms 612 KB Ok! 204 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 664 KB Ok! 2430 queries used.
2 Correct 244 ms 664 KB Ok! 2380 queries used.
3 Correct 196 ms 684 KB Ok! 2440 queries used.

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 588 ms 684 KB Number of queries more than 4500 out of 2250
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 548 ms 760 KB Number of queries more than 4000 out of 2000
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 415 ms 832 KB Number of queries more than 3550 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 298 ms 832 KB Number of queries more than 3250 out of 1625
2 Halted 0 ms 0 KB -