#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100 + 37;
const int maxm = 2e4 + 36;
struct point{
int x;
int y;
point(int x_ = 0, int y_ = 0){
x = x_, y = y_;
}
}u[maxn], s[maxn];
int n, m, c, k;
bitset<maxn> bs[maxn];
int to[maxm], cap[maxm], pre[maxm], last[maxm], pos[maxm];
int cnt = 0;
int dis[2 * maxn];
int dfs(int src, int snk, int untilnow){
if (src == snk or untilnow == 0)
return untilnow;
// cout << "# " << src << " " << untilnow << endl;
int now = 0;
for (int &ed = pos[src]; ed != -1; ed = pre[ed]){
int u = to[ed];
if (cap[ed] == 0 or dis[u] != dis[src] + 1)
continue;
int tmp = dfs(u, snk, min(cap[ed], untilnow));
cap[ed] -= tmp, cap[ed^1] += tmp;
untilnow -= tmp, now += tmp;
}
return now;
}
int Q[2 * maxn];
bool bfs(int src, int snk){
int st = 0, en = 0;
Q[en ++] = src;
memset(dis, -1, sizeof dis);
dis[src] = 0;
while (st < en){
int v = Q[st ++];
for (int ed = last[v]; ed != -1; ed = pre[ed]){
int u = to[ed];
if (dis[u] == -1 and cap[ed]){
dis[u] = dis[v] + 1;
Q[en ++] = u;
}
}
}
return dis[snk] != -1;
}
int max_flow(){
int src = n + k, snk = n + k + 1;
int ret = 0;
while (bfs(src, snk)){
for (int i = 0; i <= snk; i++)
pos[i] = last[i];
ret += dfs(src, snk, 110);
}
return ret;
}
void add_edge(int v, int u, int c){
to[cnt] = u, cap[cnt] = c, pre[cnt] = last[v], last[v] = cnt ++;
to[cnt] = v, cap[cnt] = 0, pre[cnt] = last[u], last[u] = cnt ++;
}
int sq(int x){
return x * x;
}
int dist(point a, point b){
return sq(a.x - b.x) + sq(a.y - b.y);
}
bool check(int x){
cnt = 0;
memset(last, -1, sizeof last);
int src = n + k, snk = n + k + 1;
for (int i = 0; i < n; i++)
add_edge(src, i, 1);
for (int i = 0; i < k; i++)
add_edge(i+n, snk, c);
for (int i = 0; i < n; i++){
bitset<maxn> near;
for (int j = 0; j < m; j++)
if (dist(u[i], s[j]) <= x)
near |= bs[j];
for (int j = 0; j < k; j++)
if (near[j])
add_edge(i, j+n, 1);
}
return (max_flow() == n);
}
int main(){
ios_base::sync_with_stdio(false);
cin >> n >> m >> c >> k;
for (int i = 0; i < n; i++)
cin >> u[i].x >> u[i].y;
for (int i = 0; i < m; i++)
cin >> s[i].x >> s[i].y;
for (int i = 0; i < k; i++){
int x;
cin >> x;
while (x --){
int sta;
cin >> sta;
sta --;
bs[sta][i] = 1;
}
}
int lo = -1, hi = 1e9;
while (hi - lo > 1){
int mid = (lo + hi) >> 1;
if (!check(mid))
lo = mid;
else
hi = mid;
}
if (hi == 1e9)
return cout << -1 << '\n', 0;
check(hi);
cout << hi << '\n';
int src = n + k;
for (int i = 0; i < n; i++){
int can;
for (int ed = last[i]; ed != -1; ed = pre[ed]){
int u = to[ed], c = cap[ed];
if (u != src and c == 0)
can = u - n;
}
for (int j = 0; j < m; j++){
if (!bs[j][can] or dist(u[i], s[j]) > hi)
continue;
cout << j + 1 << '\n';
break;
}
}
}
Compilation message
priglvaci.cpp: In function 'int main()':
priglvaci.cpp:133:7: warning: 'can' may be used uninitialized in this function [-Wmaybe-uninitialized]
int can;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
504 KB |
Output is correct |
| 2 |
Correct |
7 ms |
504 KB |
Output is correct |
| 3 |
Correct |
10 ms |
632 KB |
Output is correct |
| 4 |
Correct |
10 ms |
632 KB |
Output is correct |
| 5 |
Correct |
10 ms |
632 KB |
Output is correct |
| 6 |
Correct |
13 ms |
504 KB |
Output is correct |
| 7 |
Correct |
12 ms |
504 KB |
Output is correct |
| 8 |
Correct |
7 ms |
504 KB |
Output is correct |
| 9 |
Correct |
12 ms |
504 KB |
Output is correct |
| 10 |
Correct |
13 ms |
504 KB |
Output is correct |
