#include <bits/stdc++.h>
#define PB push_back
#define sz(x) ((int)x.size())
using namespace std;
typedef long double ld;
typedef long long ll;
const int N = 110;
const int M = 110;
const int K = 110;
const int MX = 210;
const int oo = 2e9;
struct edge{
int a, b, cap, flow;
edge(int _a, int _b, int _c, int _f): a(_a), b(_b), cap(_c), flow(_f) {}
};
vector<edge> edges;
vector<int> g[N], lst[K];
bool used[N];
int ux[N], uy[N], sx[M], sy[M], n, m, c, k, mt[K], ans[N];
int S, T, dst[MX], ptr[MX];
queue<int> q;
int sqr(int x) { return x * x; }
int dist(int x1, int y1, int x2, int y2){
return sqr(x1 - x2) + sqr(y1 - y2);
}
void add_edge(int a, int b, int c){
g[a].PB(sz(edges));
edges.PB({a, b, c, 0});
g[b].PB(sz(edges));
edges.PB({b, a, 0, 0});
}
bool bfs(){
fill(dst, dst + T + 1, oo);
dst[S] = 0;
q.push(S);
while (sz(q) > 0){
int v = q.front(); q.pop();
for (int nm : g[v]){
int u = edges[nm].b;
if (dst[u] == oo && edges[nm].flow < edges[nm].cap){
dst[u] = dst[v] + 1;
q.push(u);
}
}
}
return (dst[T] < oo);
}
int dfs(int v, int nw){
if (nw == 0) return 0;
if (v == T) return nw;
for (; ptr[v] < sz(g[v]); ptr[v]++){
int nm = g[v][ptr[v]];
int u = edges[nm].b;
int cur = dfs(u, min(nw, edges[nm].cap - edges[nm].flow));
if (cur > 0){
edges[nm].flow += cur;
edges[nm ^ 1].flow -= cur;
return cur;
}
}
return 0;
}
bool ok(int x){
edges.clear();
for (int i = 0; i <= T; i++)
g[i].clear();
for (int i = 0; i < n; i++)
for (int j = 0; j < k; j++){
for (int ps : lst[j])
if (dist(ux[i], uy[i], sx[ps], sy[ps]) <= x) {
add_edge(i, j + n, 1);
break;
}
}
for (int i = 0; i < n; i++)
add_edge(S, i, 1);
for (int i = 0; i < k; i++)
add_edge(i + n, T, c);
int flow = 0;
while (bfs()){
fill(ptr, ptr + T + 1, 0);
int pshd = dfs(S, oo);
while (pshd > 0){
flow += pshd;
pshd = dfs(S, oo);
}
}
return (flow == n);
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef _LOCAL
freopen("in.txt","r",stdin);
#endif // _LOCAL
cin >> n >> m >> c >> k;
S = n + k; T = n + k + 1;
if (n > c * k){
cout << -1;
return 0;
}
for (int i = 0; i < n; i++)
cin >> ux[i] >> uy[i];
for (int i = 0; i < m; i++)
cin >> sx[i] >> sy[i];
for (int i = 0; i < k; i++){
int kk; cin >> kk;
lst[i].clear();
for (int j = 0; j < kk; j++){
int x; cin >> x; x--;
lst[i].PB(x);
}
}
int l = 1, r = int(8e6);
while (l < r){
int md = (l + r) >> 1;
if (ok(md))
r = md;
else l = md + 1;
}
while (1) {}
cout << l << '\n';
ok(l);
fill(ans, ans + n, -1);
for (int i = 0; i < n; i++)
for (int nm : g[i]){
int u = edges[nm].b;
if (u == S) continue;
if (edges[nm].flow == edges[nm].cap){
ans[i] = u - n;
break;
}
}
for (int i = 0; i < n; i++) {
int id = -1;
if (ans[i] < 0){
while (1) {}
}
for (int ps : lst[ans[i]])
if (dist(ux[i], uy[i], sx[ps], sy[ps]) <= l) {
id = ps;
break;
}
cout << id + 1 << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
5 ms |
896 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Runtime error |
5 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
5 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
5 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
5 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Execution timed out |
2099 ms |
512 KB |
Time limit exceeded |
| 9 |
Runtime error |
6 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
5 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
