#include <bits/stdc++.h>
#define ABS(n) ((n) > 0 ? (n) : -(n))
#define pii pair<int, int>
using namespace std;
int N, M, C, K;
pii A[105];
pii B[105];
vector<int> bus[105];
//for macflow
vector<int> adj[205];
int cap[205][205];
int par[205];
int dist(int a, int b, int x, int y) {
return ABS(a - x) * ABS(a - x) + ABS(b - y) * ABS(b - y);
}
void edge(int u, int v, int c) {
cap[u][v] = c;
adj[u].push_back(v);
adj[v].push_back(u);
}
int bfs() {
memset(par, -1, sizeof(par));
queue<pii> q;
par[0] = -2;
q.emplace(0, 1000000);
while(!q.empty()) {
int u = q.front().first;
int flow = q.front().second;
q.pop();
for(int v : adj[u]) {
if(par[v] == -1 && cap[u][v]) {
par[v] = u;
int new_flow = min(flow, cap[u][v]);
if(v == 201) return new_flow;
q.emplace(v, new_flow);
}
}
}
return 0;
}
int maxflow() {
int flow = 0, new_flow;
while(new_flow = bfs()) {
flow += new_flow;
int u = 201;
while(u != 0) {
cap[par[u]][u] -= new_flow;
cap[u][par[u]] += new_flow;
u = par[u];
}
}
return flow;
}
void clear() {
memset(cap, 0, sizeof(cap));
adj[0].clear(), adj[201].clear();
for(int i = 1; i <= N; i++) {
adj[i].clear();
edge(0, i, 1);
}
for(int i = 1; i <= K; i++) {
adj[100 + i].clear();
edge(100 + i, 201, C);
}
}
void prepare(int mac) {
clear();
bool ok;
// cout << mac << "\n";
for(int i = 1; i <= N; i++) {
pii u = A[i];
for(int j = 1; j <= K; j++) {
ok = 0;
for(int now : bus[j]) {
pii v = B[now];
if(dist(u.first, u.second, v.first, v.second) <= mac) {
ok = 1;
break;
}
}
if(ok) {
// cout << i << " " << j << "\n";
edge(i, 100 + j, 1);
}
}
}
}
bool check(int mid) {
prepare(mid);
int res = maxflow();
// cout << mid << " " << res << "\n";
return res == N;
}
bool vis[205];
void binser() {
int l = 0, r = 2000000, res = 2000000;
while(l <= r) {
int mid = (l + r) >> 1;
if(check(mid)) {
r = mid - 1;
res = mid;
}else l = mid + 1;
}
check(res);
printf("%d\n", res);
for(int i = 1; i <= N; i++) {
pii u = A[i];
for(int j = 1; j <= K; j++) {
if(cap[j + 100][i]) {
for(int now : bus[j]) {
pii v = B[now];
if(vis[now]) continue;
if(dist(u.first, u.second, v.first, v.second) <= res) {
printf("%d\n", now);
break;
}
}
break;
}
}
}
}
void input() {
scanf("%d %d %d %d", &N, &M, &C, &K);
if(K * C < N) {
puts("-1");
exit(0);
}
int x, y, sz;
for(int i = 1; i <= N; i++) {
scanf("%d %d", &x, &y);
A[i] = make_pair(x, y);
}
for(int i = 1; i <= M; i++) {
scanf("%d %d", &x, &y);
B[i] = make_pair(x, y);
}
for(int i = 1; i <= K; i++) {
scanf("%d", &sz);
while(sz--) {
scanf("%d", &x);
bus[i].push_back(x);
}
}
}
int main() {
input();
binser();
cin >> N;
}
Compilation message
priglvaci.cpp: In function 'int maxflow()':
priglvaci.cpp:49:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
while(new_flow = bfs()) {
~~~~~~~~~^~~~~~~
priglvaci.cpp: In function 'void input()':
priglvaci.cpp:135:8: 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:142:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~~
priglvaci.cpp:146:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~~
priglvaci.cpp:150:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &sz);
~~~~~^~~~~~~~~~~
priglvaci.cpp:152:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x);
~~~~~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
512 KB |
Output is correct |
| 2 |
Correct |
8 ms |
512 KB |
Output is correct |
| 3 |
Correct |
4 ms |
384 KB |
Output is correct |
| 4 |
Correct |
16 ms |
640 KB |
Output is correct |
| 5 |
Correct |
16 ms |
640 KB |
Output is correct |
| 6 |
Correct |
15 ms |
512 KB |
Output is correct |
| 7 |
Correct |
11 ms |
512 KB |
Output is correct |
| 8 |
Correct |
6 ms |
512 KB |
Output is correct |
| 9 |
Correct |
12 ms |
640 KB |
Output is correct |
| 10 |
Correct |
10 ms |
512 KB |
Output is correct |
