Submission #57944

#	Time	Username	Problem	Language	Result	Execution time	Memory
57944		fredbr	ICC (CEOI16_icc)	C++17	7 / 100	412 ms	796 KiB

icc

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

using namespace std;

const int maxn = 110;

static int n;
static int roads = 0;
static int road[maxn][maxn];
int dx[maxn], dl[maxn];

static int getQuery(int x, int y, int l, int r)
{
	if (x > y or l > r) return 0;
	// if (roads > n-1) return false;

	for (int i = x; i <= y; i++)
		dx[i-x] = i;

	for (int i = l; i <= r; i++)
		dl[i-l] = i;


	int ans = query(y-x+1, r-l+1, dx, dl);

	// if (ans == 1 and x == y and l == r) {
	// 	cout << y-x+1 << " " << r-l+1 << "\n";
	// 	for (int i = 0; i < y-x+1; i++)
	// 		cout << dx[i] << " ";
	// 	cout << "\n";
	// 	for (int i = 0; i < r-l+1; i++)
	// 		cout << dl[i] << " ";
	// 	cout << "\n\n";
	// }
	
	return ans;
}

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;

static bool solve(int l, int r, int x, int y)
{
	if (l > r or x > y) return false;

	if (l == r and x == y) {

		if (road[l][x]) return false;

		// cout 
		if (dsu.find(l) == dsu.find(x)) return false;

		int ans = getQuery(l, l, x, x);

		if (ans == 0) return false;

		road[l][x] = 1;
		road[x][l] = 1;

		// cerr << ans << " "<< l << " " << x << "\n";
		setRoad(l, x);
		dsu.join(l, x);
		roads++;
		return true;
	}

	int ml = (l+r)/2;
	int mx = (x+y)/2;

	bool ok = false;

	// if (getQuery(l, r, x, y)) {
		
		if (getQuery(l, ml, x, mx)) ok = solve(l, ml, x, mx);

		if (ok) return true;

		if (getQuery(l, ml, mx+1, y)) ok = solve(l, ml, mx+1, y);

		if (ok) return true;

		if (getQuery(ml+1, r, x, mx)) ok = solve(ml+1, r, x, mx);

		if (ok) return true;

		if (getQuery(ml+1, r, mx+1, y)) ok = solve(ml+1, r, mx+1, y);

		if (ok) return true;
	// }

	ok = solve(l, ml, ml+1, r);

	if (ok) return true;

	ok = solve(x, mx, mx+1, y);

	return ok;
}

// bool solve1(int x, int y)
// {
// 	if (road[x][y]) return false;

// 	vector<int> xc = {x};
// 	vector<int> lc = {y};
// 	int ans = query(1, 1, xc.data(), lc.data());

// 	if (ans == 0) return false;

// 	road[x][y] = 1;
// 	road[y][x] = 1;

// 	setRoad(x, y);
// 	return true;	
// }

void run(int n)
{	
	dsu.reset(n);
	int mid = (n+1)/2;
	while (roads < n-1)
		solve(1, mid, mid+1, n);
}

Compilation message (stderr)

icc.cpp:8:12: warning: 'n' defined but not used [-Wunused-variable]
 static int n;
            ^

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