Submission #57871

#	Time	Username	Problem	Language	Result	Execution time	Memory
57871		IvanC	ICC (CEOI16_icc)	C++17	18 / 100	483 ms	900 KiB

icc

#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];

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;
}

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);
				}
				else{
					tira_matriz(i,qtd);
					marcado[i] = 0;
				}
			}
			else{
				if(resta_um()){
					segundo = acha_marcado();
					achou++;
					break;
				}
				
				int qtd = seta_cjt(i);
				if(qtd == 0){
					marcado[i] = 0;
					continue;
				}
				int resultado = query(1,qtd,cjt_a,cjt_b);
				if(resultado == 1){
					segundo = i;
					achou++;
					break;
				}
				else{
					tira_matriz(i,qtd);
					marcado[i] = 0;
				}
				
			}
			
		}
		setRoad(primeiro,segundo);
		join(primeiro,segundo);
		
	}
	
}

Compilation message (stderr)

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:121:7: warning: 'segundo' may be used uninitialized in this function [-Wmaybe-uninitialized]
   join(primeiro,segundo);
   ~~~~^~~~~~~~~~~~~~~~~~
icc.cpp:121:7: warning: 'primeiro' may be used uninitialized in this function [-Wmaybe-uninitialized]

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