Submission #55240

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
55240	2018-07-06T17:19:18 Z	IvanC	Priglavci (COCI18_priglavci)	C++17	128 / 160	22 ms	1876 KB

priglvaci

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

const int MAXN  = 2*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;
vector<int> paradas[MAXN],matches[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(matches[u].size() < C){
			pares[v] = u;
			matches[u].push_back(v);
			return 1;
		}
		else{
			for(int i = 0;i<matches[u].size();i++){
				int w = matches[u][i];
				if(bpm(w,L)){
					matches[u][i] = v;
					pares[v] = u;
					return 1;
				} 
			}
		}

	}

	return 0;
}

int max_match(int L){
	
	for(int i = 1;i<=K;i++){
		matches[i].clear();
	}
	
	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

priglvaci.cpp: In function 'int bpm(int, int)':
priglvaci.cpp:21:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(matches[u].size() < C){
      ~~~~~~~~~~~~~~~~~~^~~
priglvaci.cpp:27:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0;i<matches[u].size();i++){
                  ~^~~~~~~~~~~~~~~~~~
priglvaci.cpp: In function 'int main()':
priglvaci.cpp:60: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:63: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:66: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:70:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&qtd);
   ~~~~~^~~~~~~~~~~
priglvaci.cpp:73:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&x);
    ~~~~~^~~~~~~~~

Subtask #1

128.0 / 160.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	964 KB	Output is correct
2	Correct	4 ms	1024 KB	Output is correct
3	Correct	3 ms	1344 KB	Output is correct
4	Correct	13 ms	1344 KB	Output is correct
5	Correct	12 ms	1344 KB	Output is correct
6	Runtime error	4 ms	1344 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
7	Correct	22 ms	1876 KB	Output is correct
8	Correct	4 ms	1876 KB	Output is correct
9	Runtime error	4 ms	1876 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Correct	13 ms	1876 KB	Output is correct