oj.uz

Submission #706995

# Submission time Handle Problem Language Result Execution time Memory
706995 2023-03-08T08:43:41 Z TranGiaHuy1508 ICC (CEOI16_icc) C++17
100 / 100
 132 ms 500 KB 
#include <bits/stdc++.h>
using namespace std;

#include "icc.h"

namespace local {
	int n;
	vector<int> V, parent;
	vector<vector<int>> groups;

	int get_parent(int x){
		if (x == parent[x]) return x;
		return parent[x] = get_parent(parent[x]);
	}

	void add_edge(int x, int y){
		setRoad(x, y);

		x = get_parent(x);
		y = get_parent(y);

		for (auto i: groups[y]) groups[x].push_back(i);
		groups[y].clear();
		parent[y] = x;

		vector<int> newv;
		for (auto i: V) if (i != y) newv.push_back(i);
		V.swap(newv);

	}

	void found_solve(vector<int> &g1, vector<int> &g2){
		vector<int> tmp;
		int l = 0, r = g1.size() - 1;
		while (l < r){
			int mid = (l + r) >> 1;
			tmp.clear(); for (int i = 0; i <= mid; i++) tmp.push_back(g1[i]);
			if (query(tmp.size(), g2.size(), &tmp[0], &g2[0])) r = mid;
			else l = mid + 1;
		}
		vector<int> result = {g1[r]};
		if (g2.size() > 1){
			found_solve(g2, result);
			return;
		}
		add_edge(result[0], g2[0]);
	}

	void normal_solve(vector<int> &v){
		for (int b = 0; b < 7; b++){
			vector<int> g1, g2;
			
			for (int i = 0; i < (int)v.size(); i++){
				if ((i >> b) & 1){
					for (auto j: groups[v[i]]) g1.push_back(j);
				}
				else{
					for (auto j: groups[v[i]]) g2.push_back(j);
				}
			}

			if (query(g1.size(), g2.size(), &g1[0], &g2[0])){
				found_solve(g1, g2);
				return;
			}
		}
	}
}

void run(int N){
	local::n = N;
	local::groups.resize(local::n + 1);
	local::parent.resize(local::n + 1);
	iota(local::parent.begin(), local::parent.end(), 0);
	local::V.resize(local::n);
	iota(local::V.begin(), local::V.end(), 1);

	for (int i = 1; i <= local::n; i++) local::groups[i].push_back(i);

	for (int i = 0; i < local::n - 1; i++){
		local::normal_solve(local::V);
	}
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 468 KB Ok! 99 queries used.
2 Correct 5 ms 468 KB Ok! 97 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 476 KB Ok! 523 queries used.
2 Correct 36 ms 500 KB Ok! 653 queries used.
3 Correct 38 ms 476 KB Ok! 641 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 468 KB Ok! 1359 queries used.
2 Correct 112 ms 484 KB Ok! 1593 queries used.
3 Correct 118 ms 484 KB Ok! 1593 queries used.
4 Correct 128 ms 484 KB Ok! 1506 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 484 KB Ok! 1460 queries used.
2 Correct 105 ms 480 KB Ok! 1430 queries used.
3 Correct 111 ms 468 KB Ok! 1569 queries used.
4 Correct 114 ms 488 KB Ok! 1517 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 468 KB Ok! 1551 queries used.
2 Correct 107 ms 484 KB Ok! 1537 queries used.
3 Correct 110 ms 500 KB Ok! 1586 queries used.
4 Correct 132 ms 484 KB Ok! 1545 queries used.
5 Correct 96 ms 492 KB Ok! 1437 queries used.
6 Correct 101 ms 468 KB Ok! 1532 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 468 KB Ok! 1549 queries used.
2 Correct 131 ms 484 KB Ok! 1598 queries used.