#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
#define fi first
#define se second
#define sqr(x) ((x)*(x))
const ll INF = 1e18;
struct MaximumFlow {
// Implementation of the Edmonds-Karp algorithm.
ll n, _INF_FLOW;
vector<vector<ll>> capacity, flow, dir;
vector<vector<ll>> adj;
MaximumFlow(ll n) : n(n), _INF_FLOW(INF) {
vector<vector<ll>> _tmp = vector<vector<ll>>(n+1, vector<ll>(n+1));
capacity = flow = dir = _tmp;
adj.assign(n+1, vector<ll>(0));
}
void addEdge(ll u, ll v, ll cap) {
//cout << u << ' ' << v << ' ' << cap << '\n';
// adds a directed edge u -> v with capacity cap
dir[u][v] = 1, dir[v][u] = -1;
capacity[u][v] += cap;
adj[u].push_back(v);
adj[v].push_back(u);
}
ll bfs(ll source, ll sink, vector<ll> &parent) {
parent.assign(n+1, -1);
parent[source] = -2;
queue<pll> Q;
Q.push({source, _INF_FLOW});
while (!Q.empty()) {
ll cur, flow;
tie(cur, flow) = Q.front();
Q.pop();
for (auto &nxt : adj[cur]) {
if (parent[nxt] == -1 && capacity[cur][nxt]) {
parent[nxt] = cur;
ll newFlow = min(flow, capacity[cur][nxt]);
if (nxt == sink) {return newFlow;}
Q.push({nxt, newFlow});
}
}
}
return 0;
}
ll computeMaxflow(ll source, ll sink) {
// computes the value of the maximum flow
// the flow through each edge is stored in flow[][]
// precaution when there are multiple edges
for (ll i = 0; i <= n; i++) {
sort(adj[i].begin(), adj[i].end());
adj[i].erase(unique(adj[i].begin(), adj[i].end()), adj[i].end());
}
ll maxFlow = 0, newFlow;
vector<ll> parent(n+1);
while (newFlow = bfs(source, sink, parent)) {
maxFlow += newFlow;
ll cur = sink;
while (cur != source) {
ll prv = parent[cur];
capacity[prv][cur] -= newFlow;
capacity[cur][prv] += newFlow;
flow[prv][cur] += dir[prv][cur] * newFlow;
flow[cur][prv] += dir[cur][prv] * newFlow;
cur = prv;
}
}
return maxFlow;
}
};
const int maxN = 101;
ll N, M, C, K;
vector<pll> student(1), bus(1);
vector<ll> routes[maxN];
inline ll dist(const pll &a, const pll &b) {
return (sqr(a.fi - b.fi) + sqr(a.se - b.se));
}
int main() {
scanf("%lld %lld %lld %lld", &N, &M, &C, &K);
for (ll x, y, i = 1; i <= N; i++) {
scanf("%lld %lld", &x, &y);
student.push_back({x, y});
}
for (ll x, y, i = 1; i <= M; i++) {
scanf("%lld %lld", &x, &y);
bus.push_back({x, y});
}
for (ll k, i = 1; i <= K; i++) {
scanf("%lld", &k);
for (ll st, j = 1; j <= k; j++) {
scanf("%lld", &st);
routes[i].push_back(st);
}
}
ll L = 0, R = 8'000'000, ans = -1;
vector<vector<ll>> backtrack;
const ll _source = 1, _sink = 2;
#define STUDENT(x) (x)+2
#define ROUTE(x) (x)+N+2
while (L <= R) {
ll M = (L + R) >> 1;
//cout << M << '\n';
MaximumFlow F(N+K+2);
for (ll s = 1; s <= N; s++) {
F.addEdge(_source, STUDENT(s), 1);
}
for (ll r = 1; r <= K; r++) {
F.addEdge(ROUTE(r), _sink, C);
}
for (ll s = 1; s <= N; s++) {
for (ll r = 1; r <= K; r++) {
for (auto &b : routes[r]) {
if (dist(student[s], bus[b]) <= M) {
F.addEdge(STUDENT(s), ROUTE(r), 1);
break;
}
}
}
}
ll flow = F.computeMaxflow(_source, _sink);
if (flow != N) {
L = M + 1;
} else {
R = M - 1;
ans = M;
backtrack = F.flow;
}
}
printf("%lld\n", ans);
if (ans != -1) {
/*
for (ll s = 1; s <= N; s++) {
for (ll r = 1; r <= K; r++) {
cout << backtrack[STUDENT(s)][ROUTE(r)] << ' ';
}
cout << '\n';
}
*/
for (ll s = 1; s <= N; s++) {
for (ll r = 1; r <= K; r++) {
if (backtrack[STUDENT(s)][ROUTE(r)] == 1) {
for (auto &b : routes[r]) {
if (dist(student[s], bus[b]) <= ans) {
printf("%lld\n", b);
break;
}
}
break;
}
}
}
}
}
Compilation message
priglvaci.cpp: In member function 'll MaximumFlow::computeMaxflow(ll, ll)':
priglvaci.cpp:77:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
77 | while (newFlow = bfs(source, sink, parent)) {
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
priglvaci.cpp: In function 'int main()':
priglvaci.cpp:108:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
108 | scanf("%lld %lld %lld %lld", &N, &M, &C, &K);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
priglvaci.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
110 | scanf("%lld %lld", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
priglvaci.cpp:114:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
114 | scanf("%lld %lld", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
priglvaci.cpp:118:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
118 | scanf("%lld", &k);
| ~~~~~^~~~~~~~~~~~
priglvaci.cpp:120:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
120 | scanf("%lld", &st);
| ~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
1188 KB |
Output is correct |
| 2 |
Correct |
10 ms |
852 KB |
Output is correct |
| 3 |
Correct |
22 ms |
1144 KB |
Output is correct |
| 4 |
Correct |
22 ms |
1688 KB |
Output is correct |
| 5 |
Correct |
20 ms |
1492 KB |
Output is correct |
| 6 |
Correct |
22 ms |
2008 KB |
Output is correct |
| 7 |
Correct |
11 ms |
904 KB |
Output is correct |
| 8 |
Correct |
5 ms |
596 KB |
Output is correct |
| 9 |
Correct |
21 ms |
1580 KB |
Output is correct |
| 10 |
Correct |
11 ms |
852 KB |
Output is correct |
