oj.uz

Submission #57875

# Submission time Handle Problem Language Result Execution time Memory
57875 2018-07-16T13:14:02 Z IvanC ICC (CEOI16_icc) C++17
18 / 100
 490 ms 960 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];
vector<int> randomizado;

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;
		randomizado.push_back(i);
	}
	
	for(int vez = 1;vez<= N-1;vez++){
	
		random_shuffle(randomizado.begin(),randomizado.end());
		
		memset(marcado,0,sizeof(marcado));
		memset(matriz,0,sizeof(matriz));
		tem_marcacao = 0;
		int achou = 0,primeiro,segundo;
		for(int j = 0;j<N && achou < 2;j++){
			
			int i = randomizado[j];
			
			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

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

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 760 KB Ok! 196 queries used.
2 Correct 15 ms 760 KB Ok! 194 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 960 KB Ok! 2398 queries used.
2 Correct 178 ms 960 KB Ok! 2395 queries used.
3 Correct 208 ms 960 KB Ok! 2400 queries used.

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 490 ms 960 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 442 ms 960 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 360 ms 960 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 331 ms 960 KB Number of queries more than 3250 out of 1625
2 Halted 0 ms 0 KB -