Submission #1265886

#TimeUsernameProblemLanguageResultExecution timeMemory
1265886radhyaPriglavci (COCI18_priglavci)C++20
160 / 160
113 ms3208 KiB
// 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 timeMemoryGrader output
Fetching results...