Submission #239679

#	Time	Username	Problem	Language	Result	Execution time	Memory
239679		VEGAnn	Priglavci (COCI18_priglavci)	C++14	16 / 160	11 ms	512 KiB

priglvaci

#include <bits/stdc++.h>
#define PB push_back
using namespace std;
typedef long double ld;
typedef long long ll;
const int N = 110;
const int M = 110;
const int K = 110;
vector<int> g[N], lst[K];
bool used[N];
int ux[N], uy[N], sx[M], sy[M], n, m, c, k, mt[K], ans[N];

int sqr(int x) { return x * x; }

int dist(int x1, int y1, int x2, int y2){
    return sqr(x1 - x2) + sqr(y1 - y2);
}

bool try_kuhn(int v){
    if (used[v]) return 0;
    used[v] = 1;

    for (int u : g[v])
        if (mt[u] < 0 || try_kuhn(mt[u])){
            mt[u] = v;
            return 1;
        }
    return 0;
}

bool ok(int x){
    for (int i = 0; i < n; i++)
        g[i].clear();

    for (int i = 0; i < n; i++)
    for (int j = 0; j < k; j++){
        for (int ps : lst[j])
            if (dist(ux[i], uy[i], sx[ps], sy[ps]) <= x) {
                g[i].PB(j);
                break;
            }
    }

    fill(mt, mt + k, -1);

    for (int i = 0; i < n; i++){
        fill(used, used + n, 0);

        if (!try_kuhn(i))
            return 0;
    }

    return 1;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> m >> c >> k;

    if (n > c * k){
        cout << -1;
        return 0;
    }

    assert(c == 1);

    for (int i = 0; i < n; i++)
        cin >> ux[i] >> uy[i];

    for (int i = 0; i < m; i++)
        cin >> sx[i] >> sy[i];

    for (int i = 0; i < k; i++){
        int kk; cin >> kk;
        lst[i].clear();

        for (int j = 0; j < kk; j++){
            int x; cin >> x; x--;
            lst[i].PB(x);
        }
    }

    int l = 1, r = int(1e9);

    while (l < r){
        int md = (l + r) >> 1;

        if (ok(md))
            r = md;
        else l = md + 1;
    }

    cout << l << '\n';

    assert(ok(l));

    int cnt = 0;

    for (int i = 0; i < k; i++)
        if (mt[i] >= 0) {
            ans[mt[i]] = i;
            cnt++;
        }

    assert(cnt == n);

    for (int i = 0; i < n; i++)
        cout << ans[i] + 1 << '\n';

    return 0;
}

• Subtask 1: 16 / 160