oj.uz

Submission #239684

# Submission time Handle Problem Language Result Execution time Memory
239684 2020-06-17T07:28:24 Z VEGAnn Priglavci (COCI18_priglavci) C++14
96 / 160
 9 ms 512 KB 
#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;
    }

    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(8e6);

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

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

    cout << l << '\n';

    ok(l);

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

    for (int i = 0; i < n; i++) {
        int id = -1;

        for (int ps : lst[ans[i]])
            if (dist(ux[i], uy[i], sx[ps], sy[ps]) <= l) {
                id = ps;
                break;
            }

        cout << id + 1 << '\n';
    }

    return 0;
}

Subtask #1
96.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 9 ms 384 KB Output is correct
5 Correct 8 ms 384 KB Output is correct
6 Failed 8 ms 384 KB there exists a bus with more than C students
7 Failed 5 ms 384 KB there exists a bus with more than C students
8 Correct 6 ms 384 KB Output is correct
9 Failed 8 ms 384 KB there exists a bus with more than C students
10 Failed 5 ms 384 KB there exists a bus with more than C students