Submission #199119

#	Time	Username	Problem	Language	Result	Execution time	Memory
199119		_qVp_	Park (BOI16_park)	C++14	0 / 100	428 ms	41020 KiB

park

#include <bits/stdc++.h>

using namespace std;

const int md = 2e3 + 5;

int n, m, w, h;
int x[md], y[md], r[md], ans[5][5], dst[md][md], c[md][md], lab[md];
vector < int > adj[md];

struct edge {
    int u, v, w;
};

vector < edge > graph;

bool cmp(edge a, edge b) {
    return a.w < b.w;
}

int getRoot(int x) {
    if (lab[x] < 0)
        return x;
    return lab[x] = getRoot(lab[x]);
}

bool united(int x, int y) {
    if ((x = getRoot(x)) == (y = getRoot(y))) 
        return false;
    if (lab[x] > lab[y])
        swap(x, y);
    lab[x] += lab[y];
    lab[y] = x;
    return true;
}

void kruskal() {
    for(int i = 1; i <= n + 4; i++)
        for(int j = 1; j < i; j++)
            graph.push_back({i, j, c[i][j]});
    sort(graph.begin(), graph.end(), cmp);
    //for(int i = 0; i < graph.size(); i++)
     //   cout << graph[i].u << " " << graph[i].v << " " << graph[i].w << endl;
    for(int i = 1; i <= n + 4; i++)
        lab[i] = -1;
    
    for(int i = 0; i < graph.size(); i++) {
        int u = graph[i].u, v = graph[i].v;
        if (united(u, v)) {
        //    cout << u <<" " << v << endl;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
    }
}

void dfs(int u, int p, int root, int val) {
    dst[root][u] = val;
    for(auto &v: adj[u]) {
        if (v == p) 
            continue;
        dfs(v, u, root, max(val, c[u][v]));
    }
}

int main() {
    //freopen("test.in", "r", stdin);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m >> w >> h;
    for(int i = 1; i <= n; i++)
        cin >> x[i] >> y[i] >> r[i];

    for(int i = 1; i <= n; i++)
        for(int j = 1; j < i; j++) {
            double dist = hypot(x[j] - x[i], y[j] - y[i]) - r[i] - r[j];
            c[i][j] = c[j][i] = (int)floor(dist / 2 + 1e-10);
        }

    for(int i = 1; i <= n; i++) {
        c[i][n + 1] = c[n + 1][i] = (y[i] - r[i]) / 2;
        c[i][n + 2] = c[n + 2][i] = (x[i] - r[i]) / 2;
        c[i][n + 3] = c[n + 3][i] = (w - r[i] - x[i]) / 2;
        c[i][n + 4] = c[n + 4][i] = (h - r[i] - y[i]) / 2;
    }
    for(int i = 1; i <= 4; i++)
        for(int j = 1; j <= 4; j++)
            if (i != j)
                c[n + i][n + j] = 1e9;
    
    kruskal();

    for(int i = n + 1; i <= n + 4; i++)
        dfs(i, -1, i, 0);

    ans[1][1] = ans[2][2] = ans[3][3] = ans[4][4] = 1e9;
	ans[1][2] = ans[2][1] = min(dst[n + 1][n + 2], min(dst[n + 1][n + 3], dst[n][n + 4]));
	ans[1][3] = ans[3][1] = min(min(dst[n + 1][n + 2], dst[n + 1][n + 4]), min(dst[n + 3][n + 2], dst[n + 3][n + 4]));
	ans[1][4] = ans[4][1] = min(dst[n + 2][n + 1], min(dst[n + 2][n + 3], dst[n + 2][n + 4]));
	ans[2][3] = ans[3][2] = min(dst[n + 3][n + 1], min(dst[n + 3][n + 2], dst[n + 3][n + 4]));
	ans[2][4] = ans[4][2] = min(min(dst[n + 1][n + 3], dst[n + 1][n + 4]), min(dst[n + 2][n + 3], dst[n + 2][n + 4]));
	ans[3][4] = ans[4][3] = min(dst[n + 4][n + 1], min(dst[n + 4][n + 2], dst[n + 4][n + 3]));
	while (m--) {
        int r, e;
        cin >> r >> e;
        for(int i = 1; i <= 4; i++)
            if (ans[e][i] >= r)
                cout << i;
        cout << '\n';
    }
    return 0;
}

Compilation message (stderr)

park.cpp: In function 'void kruskal()':
park.cpp:47:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < graph.size(); i++) {
                    ~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 27
• Subtask 2: 0 / 31
• Subtask 3: 0 / 42