Submission #62875

#	Time	Username	Problem	Language	Result	Execution time	Memory
62875		IvanC	ICC (CEOI16_icc)	C++17	100 / 100	192 ms	1116 KiB

icc

#include "icc.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 110;

int pai[MAXN],N;
vector<int> filhos[MAXN];
int cjt_a[MAXN],cjt_b[MAXN],szA,szB;

int find(int x){
	if(x == pai[x]) return x;
	return pai[x] = find(pai[x]);
}

void join(int x,int y){
	x = find(x);
	y = find(y);
	if(x == y) return;
	if(x < y) swap(x,y);
	pai[y] = x;
	for(int z : filhos[y]) filhos[x].push_back(z);
}

int doQuery(vector<int> A,vector<int> B){
	if(A.empty() || B.empty()) return 0;
	szA = 0;
	szB = 0;
	memset(cjt_a,0,sizeof(cjt_a));
	memset(cjt_b,0,sizeof(cjt_b));
	for(int i : A){
		cjt_a[szA] = i;
		szA++;
	}
	for(int i : B){
		cjt_b[szB] = i;
		szB++;
	}
	return query(szA,szB,cjt_a,cjt_b);
}

int solve(vector<int> unknown_nodes, vector<int> fixed_nodes ){

	if(unknown_nodes.size() == 1) return unknown_nodes[0];

	vector<int> firstHalf,secondHalf;
	int m = unknown_nodes.size()/2;
	for(int i = 0;i<unknown_nodes.size();i++){
		if(i < m) firstHalf.push_back(unknown_nodes[i]);
		else secondHalf.push_back(unknown_nodes[i]);
	}

	if(doQuery(firstHalf,fixed_nodes)) return solve(firstHalf,fixed_nodes);
	else return solve(secondHalf,fixed_nodes);

}

int test_partition(int bit,vector<int>& A,vector<int>& B,vector<int> possible,int flag){
	for(int i = 0;i<possible.size();i++){
		int j = possible[i];
		if(i & (1 << bit)){
			for(int k : filhos[j]) A.push_back(k);
		}
		else{
			for(int k : filhos[j]) B.push_back(k);
		}
	}
	if(flag) return 1;
	else return doQuery(A,B);
}

void discover_edge(){

	vector<int> possiveis,quaisbits,A,B;

	for(int i = 1;i<=N;i++){
		if(find(i) == i) possiveis.push_back(i);
	}

	for(int i = 0;(1 << i) <= possiveis.size();i++) quaisbits.push_back(i);
	random_shuffle(quaisbits.begin(),quaisbits.end());

	for(int j = 0;j<quaisbits.size();j++){
		A.clear();
		B.clear();
		int i = quaisbits[j],flag = (j == quaisbits.size() - 1);
		if(!test_partition(i,A,B,possiveis,flag)) continue;
		int x = solve(A,B);
		int y = solve(B,A);
		join(x,y);
		setRoad(x,y);
		break;
	}

}

void run(int n){
	N = n;

	for(int i = 1;i<=N;i++){
		pai[i] = i;
		filhos[i].push_back(i);
	}

	for(int i = 1;i<N;i++){
		discover_edge();
	}

}

Compilation message (stderr)

icc.cpp: In function 'int solve(std::vector<int>, std::vector<int>)':
icc.cpp:48:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<unknown_nodes.size();i++){
                ~^~~~~~~~~~~~~~~~~~~~~
icc.cpp: In function 'int test_partition(int, std::vector<int>&, std::vector<int>&, std::vector<int>, int)':
icc.cpp:59:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<possible.size();i++){
                ~^~~~~~~~~~~~~~~~
icc.cpp: In function 'void discover_edge()':
icc.cpp:80:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;(1 << i) <= possiveis.size();i++) quaisbits.push_back(i);
                ~~~~~~~~~^~~~~~~~~~~~~~~~~~~
icc.cpp:83:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 0;j<quaisbits.size();j++){
                ~^~~~~~~~~~~~~~~~~
icc.cpp:86:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   int i = quaisbits[j],flag = (j == quaisbits.size() - 1);
                                ~~^~~~~~~~~~~~~~~~~~~~~~~

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