//I love armpit fetish
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"
#define x first
#define y second
typedef pair<int, int> point;
const int MAX_N = 302;
const int INF = 1e9;
int n, m, bus_capacity, nBus, c[MAX_N][MAX_N], f[MAX_N][MAX_N];
int source, target, d[MAX_N], nTime, visited[MAX_N];
vector<int> bus[MAX_N], g[MAX_N];
point bus_stop[MAX_N], student[MAX_N];
int sqr(int x) {
return x * x;
}
int dist(point p, point q) {
return sqr(p.x - q.x) + sqr(p.y - q.y);
}
int dist(int bus_id, point s) {
int res = INF;
for (int i=0; i<bus[bus_id].size(); ++i) {
int u = bus[bus_id][i];
res = min(res, dist(bus_stop[u], s));
}
return res;
}
void enter() {
cin >> n >> m >> bus_capacity >> nBus;
for (int i=1; i<=n; ++i)
cin >> student[i].x >> student[i].y;
for (int i=1; i<=m; ++i)
cin >> bus_stop[i].x >> bus_stop[i].y;
for (int i=1; i<=nBus; ++i) {
int k; cin >> k;
while (k--) {
int x; cin >> x;
bus[i].push_back(x);
}
}
}
void init_graph(int weakness) {
source = 1;
target = nBus + n + 2;
for (int i=source; i<=target; ++i)
g[i].clear();
memset(c, 0, sizeof(c));
memset(f, 0, sizeof(f));
for (int i=2; i<=nBus+1; ++i) {
g[source].push_back(i);
g[i].push_back(source);
c[source][i] = bus_capacity;
}
for (int i=nBus+2; i<=nBus+n+1; ++i) {
g[target].push_back(i);
g[i].push_back(target);
c[i][target] = 1;
}
for (int i=1; i<=nBus; ++i) {
for (int j=1; j<=n; ++j) {
if (dist(i, student[j])<=weakness) {
g[i+1].push_back(j+nBus+1);
g[j+nBus+1].push_back(i+1);
c[i+1][j+nBus+1] = 1;
}
}
}
}
bool bfs() {
memset(d, 0, sizeof(d));
d[source] = 1;
queue<int> qu;
qu.push(source);
while (qu.size()) {
int u = qu.front();
qu.pop();
if (u==target)
return true;
for (int i=0; i<g[u].size(); ++i) {
int v = g[u][i];
if (d[v]==0 && c[u][v]>f[u][v]) {
d[v] = d[u] + 1;
qu.push(v);
}
}
}
return false;
}
int find_path(int u, int delta) {
if (visited[u] != nTime)
visited[u] = nTime;
else
return 0;
if (u==target)
return delta;
for (int i=0; i<g[u].size(); ++i) {
int v = g[u][i];
if (d[v]==d[u] + 1 && c[u][v]>f[u][v]) {
int x = find_path(v, min(delta, c[u][v]-f[u][v]));
if (x>0) {
f[u][v] += x;
f[v][u] -= x;
return x;
}
}
}
return 0;
}
int max_flow(int weakness) {
init_graph(weakness);
// PR0(g[3], g[3].size());
// debug(c[4][5]);
int res = 0;
while (bfs()) {
while (true) {
++nTime;
int x = find_path(source, INF);
if (x==0)
break;
res += x;
//assert(res<=n);
}
}
return res;
}
int bisect() {
int l = 0, r = INF, mid = (l + r) / 2;
while (l!=mid && mid!=r) {
if (max_flow(mid) == n)
r = mid;
else
l = mid;
mid = (l + r) / 2;
}
for (int i=l; i<=r; ++i)
if (max_flow(i) == n)
return i;
}
void trace(int x) {
cout << x << '\n';
for (int i=nBus+2; i<=nBus+n+1; ++i) {
for (int j=2; j<=nBus+1; ++j) {
if (f[j][i]==1) {
int pos = 0;
for (int t=0; t<bus[j-1].size(); ++t) {
int id = bus[j-1][t];
if (dist(bus_stop[id], student[i-nBus-1])<=x)
pos = id;
}
cout << pos << '\n';
break;
}
}
}
}
int main() {
//#define OFFLINE_JUDGE doraemon
#ifdef OFFLINE_JUDGE
freopen(FILE_NAME".inp", "r", stdin);
freopen(FILE_NAME".out", "w", stdout);
#endif
ios::sync_with_stdio(0); cin.tie(0);
enter();
if (bus_capacity * nBus < n) {
cout << -1;
return 0;
}
//debug(max_flow(4));
int x = bisect();
trace(x);
}
Compilation message
priglvaci.cpp: In function 'int dist(int, point)':
priglvaci.cpp:34:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<bus[bus_id].size(); ++i) {
~^~~~~~~~~~~~~~~~~~~
priglvaci.cpp: In function 'bool bfs()':
priglvaci.cpp:94:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<g[u].size(); ++i) {
~^~~~~~~~~~~~
priglvaci.cpp: In function 'int find_path(int, int)':
priglvaci.cpp:112:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<g[u].size(); ++i) {
~^~~~~~~~~~~~
priglvaci.cpp: In function 'void trace(int)':
priglvaci.cpp:164:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int t=0; t<bus[j-1].size(); ++t) {
~^~~~~~~~~~~~~~~~
priglvaci.cpp: In function 'int bisect()':
priglvaci.cpp:156:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
1144 KB |
Output is correct |
| 2 |
Correct |
9 ms |
1144 KB |
Output is correct |
| 3 |
Correct |
2 ms |
1144 KB |
Output is correct |
| 4 |
Correct |
28 ms |
1200 KB |
Output is correct |
| 5 |
Correct |
22 ms |
1376 KB |
Output is correct |
| 6 |
Correct |
22 ms |
1376 KB |
Output is correct |
| 7 |
Correct |
11 ms |
1376 KB |
Output is correct |
| 8 |
Correct |
7 ms |
1376 KB |
Output is correct |
| 9 |
Correct |
15 ms |
1376 KB |
Output is correct |
| 10 |
Correct |
16 ms |
1376 KB |
Output is correct |
