Submission #1265883

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265883		radhya	Priglavci (COCI18_priglavci)	C++20	160 / 160	114 ms	3204 KiB

priglvaci

// 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();
    }
}

• Subtask 1: 160 / 160