oj.uz

Submission #62875

# Submission time Handle Problem Language Result Execution time Memory
62875 2018-07-30T15:33:33 Z IvanC ICC (CEOI16_icc) C++17
100 / 100
 192 ms 1116 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 10 ms 504 KB Ok! 101 queries used.
2 Correct 10 ms 624 KB Ok! 97 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 704 KB Ok! 523 queries used.
2 Correct 65 ms 704 KB Ok! 643 queries used.
3 Correct 67 ms 712 KB Ok! 644 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 772 KB Ok! 1445 queries used.
2 Correct 152 ms 772 KB Ok! 1599 queries used.
3 Correct 143 ms 940 KB Ok! 1568 queries used.
4 Correct 146 ms 940 KB Ok! 1545 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 940 KB Ok! 1554 queries used.
2 Correct 192 ms 940 KB Ok! 1565 queries used.
3 Correct 149 ms 940 KB Ok! 1571 queries used.
4 Correct 156 ms 940 KB Ok! 1503 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 940 KB Ok! 1585 queries used.
2 Correct 153 ms 940 KB Ok! 1584 queries used.
3 Correct 165 ms 940 KB Ok! 1592 queries used.
4 Correct 173 ms 940 KB Ok! 1580 queries used.
5 Correct 170 ms 940 KB Ok! 1489 queries used.
6 Correct 187 ms 940 KB Ok! 1563 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 984 KB Ok! 1591 queries used.
2 Correct 173 ms 1116 KB Ok! 1589 queries used.