oj.uz

Submission #55263

# Submission time Handle Problem Language Result Execution time Memory
55263 2018-07-06T18:50:56 Z IvanC Priglavci (COCI18_priglavci) C++17
160 / 160
 4 ms 1360 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],onibus[MAXN];
int capacidade[MAXN],par[MAXN],visitado[MAXN];
int N,M,C,K;

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) continue;
		par[v] = u;
		capacidade[u]--;
		return 1;
	}
	for(int w = 1;w<=N;w++){
		int u = par[w];
		if(u == -1) continue;
		if(menor[v][u] > L) continue;
		if(!bpm(w,L)) continue;
		par[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++) par[i] = -1;

	for(int i = 1;i<=N;i++){
		memset(visitado,0,sizeof(visitado));
		if(!bpm(i,L)) return 0;
	}

	return 1;

}

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

int main(){

	cin >> N >> M >> C >> K;

	for(int i = 1;i<=N;i++){
		cin >> X[i] >> Y[i];
	}
	for(int i = 1;i<=M;i++){
		cin >> pX[i] >> pY[i];
	}
	for(int i = 1;i<=K;i++){
		int ki;
		cin >> ki;
		for(int j = 1;j<=ki;j++){
			int x;
			cin >> x;
			onibus[x] = i;
		}
	}

	for(int i = 1;i<=N;i++){
		
		for(int j = 1;j<=K;j++) menor[i][j] = 2*INF;

		for(int j = 1;j<=M;j++){
			int distancia = sq(X[i] - pX[j]) + sq(Y[i] - pY[j]);
			if(distancia < menor[i][onibus[j]]){
				qual[i][onibus[j]] = j;
				menor[i][onibus[j]] = distancia;
			}
 		}

	}

	if(!max_match(INF)){
		cout << -1 << endl;
		return 0;
	}

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

	max_match(resposta);
	cout << resposta << endl;
	for(int i = 1;i<=N;i++) cout << qual[i][par[i]] << endl;

	return 0;
}

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 760 KB Output is correct
2 Correct 3 ms 760 KB Output is correct
3 Correct 4 ms 1308 KB Output is correct
4 Correct 4 ms 1308 KB Output is correct
5 Correct 4 ms 1308 KB Output is correct
6 Correct 4 ms 1308 KB Output is correct
7 Correct 3 ms 1308 KB Output is correct
8 Correct 3 ms 1308 KB Output is correct
9 Correct 3 ms 1308 KB Output is correct
10 Correct 3 ms 1360 KB Output is correct