// radhya 01 Sep 2025
#include<bits/stdc++.h>
using namespace std;
// helpers to detect container and map
template<typename T>
auto is_iterable_impl(int) -> decltype(begin(declval<T>()), end(declval<T>()), true_type{});
template<typename T>
false_type is_iterable_impl(...);
template<typename T>
using is_iterable = decltype(is_iterable_impl<T>(0));
template<typename T, typename = void>
struct is_map_like : false_type {};
template<typename T>
struct is_map_like<T, void_t<typename T::key_type, typename T::mapped_type>> : true_type {};
// pair printer
template<typename T1, typename T2>
ostream& operator<<(ostream &os, const pair<T1, T2> &p) {
return os << "(" << p.first << ", " << p.second << ")";
}
// tuple printer
template<size_t Index = 0, typename... Ts>
enable_if_t<Index == sizeof...(Ts)> print_tuple(ostream&, const tuple<Ts...>&) {}
template<size_t Index = 0, typename... Ts>
enable_if_t<Index < sizeof...(Ts)>
print_tuple(ostream& os, const tuple<Ts...> &t) {
if (Index > 0) os << ", ";
os << get<Index>(t);
print_tuple<Index + 1>(os, t);
}
template<typename... Ts>
ostream& operator<<(ostream &os, const tuple<Ts...> &t) {
os << "(";
print_tuple(os, t);
return os << ")";
}
// map-like printer
template<typename M>
enable_if_t<is_map_like<M>::value, ostream&>
operator<<(ostream &os, const M &m) {
os << "{";
bool first = true;
for (const auto &kv : m) {
if (!first) os << ", ";
os << kv.first << ": " << kv.second;
first = false;
}
return os << "}";
}
// iterable printer
template<typename C>
enable_if_t<is_iterable<C>::value && !is_same_v<C, string> && !is_map_like<C>::value, ostream&>
operator<<(ostream &os, const C &c){
os << "{";
bool first = true;
for (const auto &e : c) {
if (!first) os << ", ";
os << e;
first = false;
}
return os << "}";
}
#ifndef LOCAL
#define deb(...) 0
template <typename... Args> void rep1(Args&&... args) {}
template <typename... Args> void rep2(Args&&... args) {}
template <typename... Args> void rep3(Args&&... args) {}
#else
const bool debugging = true;
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template <typename... Args> void logger(string vars, Args &&...values) {
if(!debugging) return;
cout << "==| ";
cout << vars << " = ";
string delim = "";
(..., (cout << delim << values, delim = ", "));
cout << "\n";
}
template <typename... Args> void print(string prefix, Args&&... args) {
cout << prefix << ' ';
((cout << args << ' '), ...);
cout << '\n';
}
template <typename... Args> void rep1(Args&&... args) { print("==>", forward<Args>(args)...); }
template <typename... Args> void rep2(Args&&... args) { print("==>>>", forward<Args>(args)...); }
template <typename... Args> void rep3(Args&&... args) { print("==>>>>>", forward<Args>(args)...); }
#endif
#define ll long long
#define ld long double
#define fi first
#define se second
#define mp make_pair
#define mt make_tuple
const int maxn = 105;
int n, m, c, k;
vector<pair<int, int>> stud(1), stop(1);
int route[maxn];
struct maxflow {
int n;
vector<vector<ll>> cap;
vector<vector<int>> adj;
set<pair<int, int>> edgs;
maxflow(int _n) : n(_n) {
cap.resize(n, vector<ll>(n, 0ll));
adj.resize(n, vector<int>());
}
void join(int u, int v, ll w) {
if(!edgs.count(mp(u, v))) {
adj[u].push_back(v);
adj[v].push_back(u);
edgs.insert(mp(u, v));
edgs.insert(mp(v, u));
}
cap[u][v] += w;
}
tuple<ll, vector<vector<ll>>> edmond_karp(int source, int sink) {
ll flow = 0;
vector<vector<ll>> flw(n, vector<ll>(n, 0ll));
while(true) {
auto [cflow, path] = bfs(source, sink, flw);
if(path.empty()) break;
flow += cflow;
int now = source;
for(auto chd : path) {
flw[now][chd] += cflow;
flw[chd][now] -= cflow;
now = chd;
}
}
return mt(flow, flw);
}
tuple<ll, vector<int>> bfs(int source, int sink, vector<vector<ll>> &flw) {
ll flow = 0;
vector<int> path;
vector<ll> mxv(n, 0);
vector<int> prv(n, -1);
queue<int> q;
q.push(source);
prv[source] = 0;
mxv[source] = LLONG_MAX;
while(!q.empty()) {
auto now = q.front();
q.pop();
if(now == sink) {
while(now != source) {
path.push_back(now);
now = prv[now];
}
reverse(path.begin(), path.end());
break;
}
for(auto chd : adj[now]) {
ll rem = cap[now][chd] - flw[now][chd];
if(prv[chd] != -1 || rem == 0) continue;
prv[chd] = now;
mxv[chd] = min(mxv[now], rem);
q.push(chd);
}
}
return mt(mxv[sink], path);
}
};
void setup() {
}
int dis(pair<int, int> a, pair<int, int> b) {
int x = a.fi - b.fi;
int y = a.se - b.se;
deb(a, b, x*x + y*y);
return x*x + y*y;
}
bool cek(int mid) {
auto model = maxflow(n+m+k+2);
for(int i = 1; i <= n; i++) {
model.join(0, i, 1);
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(dis(stud[i], stop[j]) <= mid) {
model.join(i, j+n, 1);
}
}
}
for(int j = 1; j <= m; j++) {
model.join(j+n, route[j]+n+m, c);
}
for(int i = 1; i <= k; i++) {
model.join(i+n+m, n+m+k+1, c);
}
return get<0>(model.edmond_karp(0, n+m+k+1)) == n;
}
void loop() {
cin >> n >> m >> c >> k;
for(int i = 1; i <= n; i++) {
int x, y; cin >> x >> y;
stud.emplace_back(x, y);
}
for(int j = 1; j <= m; j++) {
int x, y; cin >> x >> y;
stop.emplace_back(x, y);
}
for(int i = 1; i <= k; i++) {
int ki; cin >> ki;
for(int j = 1; j <= ki; j++) {
int u; cin >> u;
route[u] = i;
}
}
int l = 0, r = 1e7;
while(l < r) {
int mid = (l + r) / 2;
if(cek(mid)) {
r = mid;
}
else {
l = mid+1;
}
}
if(l == 1e7) {
cout << -1 << '\n';
}
else {
int ans = l;
auto model = maxflow(n+m+k+2);
for(int i = 1; i <= n; i++) {
model.join(0, i, 1);
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(dis(stud[i], stop[j]) <= ans) {
model.join(i, j+n, 1);
}
}
}
for(int j = 1; j <= m; j++) {
model.join(j+n, route[j]+n+m, c);
}
for(int i = 1; i <= k; i++) {
model.join(i+n+m, n+m+k+1, c);
}
auto mtx = get<1>(model.edmond_karp(0, n+m+k+1));
cout << ans << '\n';
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(mtx[i][j+n] > 0) cout << j << '\n';
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int tc = 1;
setup();
while(tc--) {
loop();
}
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
