oj.uz

Submission #55243

# Submission time Handle Problem Language Result Execution time Memory
55243 2018-07-06T17:33:49 Z IvanC Priglavci (COCI18_priglavci) C++17
128 / 160
 3 ms 1684 KB 
#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

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.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 1176 KB Output is correct
4 Correct 2 ms 1176 KB Output is correct
5 Correct 3 ms 1176 KB Output is correct
6 Runtime error 3 ms 1176 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Correct 3 ms 1532 KB Output is correct
8 Correct 2 ms 1532 KB Output is correct
9 Runtime error 3 ms 1532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Correct 3 ms 1684 KB Output is correct