oj.uz

Submission #58054

# Submission time Handle Problem Language Result Execution time Memory
58054 2018-07-16T16:39:33 Z IvanC ICC (CEOI16_icc) C++17
0 / 100
 27 ms 944 KB 
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 110;
 
int matriz[MAXN][MAXN],pai[MAXN],n;
int cjt_a[MAXN],cjt_b[MAXN],tem_marcacao,marcado[MAXN],cjt_aux[MAXN];
 
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;	
}
 
int seta_cjt(int v){
	if(tem_marcacao && !marcado[v]) return 0;
	memset(cjt_a,0,sizeof(cjt_a));
	memset(cjt_b,0,sizeof(cjt_b));
	cjt_a[0] = v;
	int ptr = 0;
	for(int i = 1;i<=n;i++){
		if(find(i) != find(v) && !matriz[i][v]){
			cjt_b[ptr] = i;
			ptr++;
		}
	}
	return ptr;
}
 
void tira_matriz(int v,int ptr){
	for(int i = 0;i<ptr;i++){
		int u = cjt_b[i];
		matriz[v][u] = matriz[u][v] = 1;
	}
}
 
void marca_tudo(int ptr){
	tem_marcacao = 1;
	for(int i = 0;i<ptr;i++){
		int u = cjt_b[i];
		marcado[u] = 1;
	}
}
 
int resta_um(){
	int total = 0;
	for(int i = 1;i<=n;i++){
		if(marcado[i]) total++;
	}
	return total == 1;
}
 
int acha_marcado(){
	for(int i = 1;i<=n;i++) if(marcado[i]) return i;
}

int seta_cjt(vector<int> davez){
	memset(cjt_aux,0,sizeof(cjt_aux));
	int ptr = 0;
	for(int i : davez){
		cjt_aux[ptr] = i;
		ptr++;
	}
	return ptr;
}
 
 int divide(int v,int ptr){
 	vector<int> vetorzao;
 	for(int i = 0;i<ptr;i++){
 		vetorzao.push_back(cjt_b[i]);
 	}
 	while(vetorzao.size() > 1){
 		 vector<int> outro;
 		 int tx = outro.size()/2;
		  for(int i = 0;i<tx;i++){
 		 	outro.push_back(vetorzao.back());
 		 	vetorzao.pop_back();
 		 }
 		 int qtd = seta_cjt(outro);
 		 if(query(1,qtd,cjt_a,cjt_aux)){
 		 	vetorzao = outro;
 		 }

 	}
 	return vetorzao[0];
 }
 
void run(int N){
	n = N;
	for(int i = 1;i<=N;i++){
		pai[i] = i;
	}
	
	for(int vez = 1;vez<= N-1;vez++){
		
		memset(marcado,0,sizeof(marcado));
		memset(matriz,0,sizeof(matriz));
		tem_marcacao = 0;
		int achou = 0,primeiro,segundo;
		for(int i = 1;i<=N && achou < 2;i++){
			
			if(achou == 0){
				int qtd = seta_cjt(i);
				if(qtd == 0) continue;
				int resultado = query(1,qtd,cjt_a,cjt_b);
				if(resultado == 1){
					achou++;
					tem_marcacao = 1;
					primeiro = i;
					marca_tudo(qtd);
					segundo = divide(i,qtd);
					break;
				}
				else{
					tira_matriz(i,qtd);
					marcado[i] = 0;
				}
			}
			
		}
		setRoad(primeiro,segundo);
		join(primeiro,segundo);
		
	}
	
}

Compilation message

icc.cpp: In function 'int acha_marcado()':
icc.cpp:63:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
icc.cpp: In function 'void run(int)':
icc.cpp:130:7: warning: 'segundo' may be used uninitialized in this function [-Wmaybe-uninitialized]
   join(primeiro,segundo);
   ~~~~^~~~~~~~~~~~~~~~~~
icc.cpp:130:7: warning: 'primeiro' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 504 KB Number of queries more than 3000 out of 1500
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 612 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 21 ms 944 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 24 ms 944 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 27 ms 944 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 20 ms 944 KB Number of queries more than 3250 out of 1625
2 Halted 0 ms 0 KB -