oj.uz

답안 #239704

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
239704 2020-06-17T08:00:41 Z VEGAnn Priglavci (COCI18_priglavci) C++14
160 / 160
 10 ms 820 KB 
#include <bits/stdc++.h>
#define PB push_back
#define sz(x) ((int)x.size())
using namespace std;
typedef long double ld;
typedef long long ll;
const int N = 110;
const int M = 110;
const int K = 110;
const int MX = 1010;
const int oo = 2e9;

struct edge{
    int a, b, cap, flow;

    edge(int _a, int _b, int _c, int _f): a(_a), b(_b), cap(_c), flow(_f) {}
};

vector<edge> edges;

vector<int> g[MX], lst[K];
bool used[N];
int ux[N], uy[N], sx[M], sy[M], n, m, c, k, ans[N];
int S, T, dst[MX], ptr[MX];
queue<int> q;

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

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

void add_edge(int a, int b, int c){
    g[a].PB(sz(edges));
    edges.PB({a, b, c, 0});

    g[b].PB(sz(edges));
    edges.PB({b, a, 0, 0});
}

bool bfs(){
    fill(dst, dst + T + 1, oo);

    dst[S] = 0;
    q.push(S);

    while (sz(q) > 0){
        int v = q.front(); q.pop();

        for (int nm : g[v]){
            int u = edges[nm].b;

            if (dst[u] == oo && edges[nm].flow < edges[nm].cap){
                dst[u] = dst[v] + 1;
                q.push(u);
            }
        }
    }

    return (dst[T] < oo);
}

int dfs(int v, int nw){
    if (nw == 0) return 0;

    if (v == T) return nw;

    for (; ptr[v] < sz(g[v]); ptr[v]++){
        int nm = g[v][ptr[v]];
        int u = edges[nm].b;

        if (dst[u] - 1 != dst[v]) continue;

        int cur = dfs(u, min(nw, edges[nm].cap - edges[nm].flow));

        if (cur > 0){
            edges[nm].flow += cur;
            edges[nm ^ 1].flow -= cur;
            return cur;
        }
    }

    return 0;
}

bool ok(int x){
    edges.clear();

    for (int i = 0; i <= T; 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) {
                add_edge(i, j + n, 1);
                break;
            }
    }

    for (int i = 0; i < n; i++)
        add_edge(S, i, 1);

    for (int i = 0; i < k; i++)
        add_edge(i + n, T, c);

    int flow = 0;

    while (bfs()){
        fill(ptr, ptr + T + 1, 0);

        int pshd = dfs(S, oo);

        while (pshd > 0){
            flow += pshd;
            pshd = dfs(S, oo);
        }
    }

    return (flow == n);
}

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;

    S = n + k; T = n + k + 1;

    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);

    fill(ans, ans + n, -1);

    for (int i = 0; i < n; i++)
    for (int nm : g[i]){
        int u = edges[nm].b;

        if (u == S) continue;

        if (edges[nm].flow == edges[nm].cap){
            ans[i] = u - n;
            break;
        }
    }

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

        if (ans[i] < 0){
            while (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
160.0 / 160.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 820 KB Output is correct
2 Correct 7 ms 640 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 9 ms 820 KB Output is correct
5 Correct 10 ms 816 KB Output is correct
6 Correct 9 ms 768 KB Output is correct
7 Correct 7 ms 512 KB Output is correct
8 Correct 6 ms 512 KB Output is correct
9 Correct 8 ms 816 KB Output is correct
10 Correct 6 ms 512 KB Output is correct