oj.uz

Submission #57944

# Submission time Handle Problem Language Result Execution time Memory
57944 2018-07-16T14:17:36 Z fredbr ICC (CEOI16_icc) C++17
7 / 100
 412 ms 796 KB 
#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

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

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 580 KB Ok! 305 queries used.
2 Correct 21 ms 644 KB Ok! 297 queries used.

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 283 ms 708 KB Number of queries more than 5000 out of 2500
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 407 ms 748 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 412 ms 748 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 347 ms 792 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 270 ms 796 KB Number of queries more than 3250 out of 1625
2 Halted 0 ms 0 KB -