Submission #55243

#	Time	Username	Problem	Language	Result	Execution time	Memory
55243		IvanC	Priglavci (COCI18_priglavci)	C++17	128 / 160	3 ms	1684 KiB

priglvaci

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

const int MAXN  = 1e3 + 10;
const int INF = 4*1e6 + 10;

int X[MAXN],Y[MAXN],pX[MAXN],pY[MAXN],menor[MAXN][MAXN],qual[MAXN][MAXN],visitado[MAXN],pares[MAXN],N,M,C,K;
int capacidade[MAXN];
vector<int> paradas[MAXN];

int sq(int x){return x*x;}

int bpm(int v,int L){
	
	if(visitado[v]) return 0;
	visitado[v] = 1;
	
	for(int u = 1;u<=K;u++){
		if(menor[v][u] > L) continue;
		if(capacidade[u] > 0){
			capacidade[u]--;
			pares[v] = u;
			return 1;
		}
	}
	for(int w = 1;w<=N;w++){
		if(pares[w] == -1) continue;
		int u = pares[w];
		if(menor[v][u] > L) continue;
		if(bpm(w,L)){
			pares[v] = u;
			return 1;
 		}
	}

	return 0;

}

int max_match(int L){
	
	for(int i = 1;i<=K;i++){
		capacidade[i] = C;
	}
	
	for(int i = 1;i<=N;i++) pares[i] = -1;
	
	for(int i = 1;i<=N;i++){
		memset(visitado,0,sizeof(visitado));
		if(!bpm(i,L)) return 0;
	}

	return 1;
}

int main(){

	scanf("%d %d %d %d",&N,&M,&C,&K);

	for(int i = 1;i<=N;i++){
		scanf("%d %d",&X[i],&Y[i]);
	}
	for(int i = 1;i<=M;i++){
		scanf("%d %d",&pX[i],&pY[i]);
	}
	for(int i = 1;i<=K;i++){
		int qtd;
		scanf("%d",&qtd);
		for(int j = 1;j<=qtd;j++){
			int x;
			scanf("%d",&x);
			paradas[i].push_back(x);
		}
	}

	for(int i = 1;i<=N;i++){
		for(int j = 1;j<=K;j++){
			menor[i][j] = sq(X[i] - pX[paradas[j][0]]) + sq(Y[i] - pY[paradas[j][0]]);
			qual[i][j] = paradas[j][0];
			for(int p : paradas[j]){
				int custo  = sq(X[i] - pX[p]) + sq(Y[i] - pY[p]);
				if(custo < menor[i][j]){
					menor[i][j] = custo;
					qual[i][j] = p;
				}
			}
		}
	}

	if(!max_match(INF)){
		printf("-1\n");
		return 0;
	}

	int ini = 0,fim = INF,meio,resposta = INF;
	while(ini <= fim){
		meio = (ini+fim)/2;
		if(max_match(meio)){
			resposta = meio;
			fim = meio - 1;
		}
		else{
			ini = meio + 1;
		}
	}

	max_match(resposta);
	printf("%d\n",resposta);
	for(int i = 1;i<=N;i++) printf("%d\n",qual[i][pares[i]]);

	return 0;
}

Compilation message (stderr)

priglvaci.cpp: In function 'int main()':
priglvaci.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d %d",&N,&M,&C,&K);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
priglvaci.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&X[i],&Y[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~
priglvaci.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&pX[i],&pY[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
priglvaci.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&qtd);
   ~~~~~^~~~~~~~~~~
priglvaci.cpp:71:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&x);
    ~~~~~^~~~~~~~~

• Subtask 1: 128 / 160