Submission #1220425

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220425		beaconmc	Park (BOI16_park)	C++20	100 / 100	1749 ms	83012 KiB

park

#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define ff first
#define ss second
#define int long long
#define float double
#define ld long double

float adjmatrix[2010][2010];
const float maxn = 10000000000000;


float connection(int a, int b) {
    vector<float> dist(2010, maxn);
    priority_queue<pair<float, int>, vector<pair<float, int>>, greater<pair<float, int>>> pq;
    pq.push(mp((float)0, a));
    pair<float, int> node;
    while (pq.size() > 0) {
        node = pq.top(); pq.pop();
        if (dist[node.ss] != maxn) continue;
        dist[node.ss] = node.ff;
        for (int i=0;i<2010;i++) {
            if (dist[i] != maxn || adjmatrix[node.ss][i] == -1) continue;
            pq.push(mp(max(adjmatrix[node.ss][i], dist[node.ss]), i));
        }
    }

    return dist[b];
}


void susconnection(int a, int b, int c, int d, float &valb, float &valc, float &vald) {
    vector<float> dist(2010, maxn);
    priority_queue<pair<float, int>, vector<pair<float, int>>, greater<pair<float, int>>> pq;
    pq.push(mp((float)0, a));
    pair<float, int> node;
    while (pq.size() > 0) {
        node = pq.top(); pq.pop();
        if (dist[node.ss] != maxn) continue;
        dist[node.ss] = node.ff;
        for (int i=0;i<2010;i++) {
            if (dist[i] != maxn || adjmatrix[node.ss][i] == -1) continue;
            pq.push(mp(max(adjmatrix[node.ss][i], dist[node.ss]), i));
        }
    }

    valb = dist[b];
    valc = dist[c];
    vald = dist[d];
}


bool check(int a, int b, vector<float> wall, int r) {
    if (a == b) return true;
    if (wall[a] >= 2*r && wall[b] >= 2*r) {
        if (abs(a - b) == 2) {
            if (wall[5] >= 2*r && wall[6] >= 2*r) return true;
        } else {
            if (a/3 == b/3) {
                if (wall[5] >= 2*r) return true;
            } else {
                if (wall[6] >= 2*r) return true;
            }
        }
    }
    return false;
}


int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    for (int i=0;i<2010;i++) {
        for (int j=0;j<2010;j++) {
            adjmatrix[i][j] = -1;
        }
    }


    int n, m, w, h; cin >> n >> m >> w >> h;
    vector<vector<int>> trees(n, vector<int>(3));
    vector<pair<int,int>> visitors(m);
    for (int i=0;i<n;i++) {
        cin >> trees[i][0] >> trees[i][1] >> trees[i][2];
    }
    for (int i=0;i<m;i++) {
        cin >> visitors[i].ff >> visitors[i].ss;
    }


    for (int i=0;i<n;i++) {
        for (int j=0;j<n;j++) {
            if (i == j) continue;
            adjmatrix[i][j] = sqrt((trees[i][0] - trees[j][0])*(trees[i][0] - trees[j][0]) + (trees[i][1] - trees[j][1])*(trees[i][1] - trees[j][1])) - trees[i][2] - trees[j][2];
        }
    }
    for (int i=0;i<n;i++) {
        adjmatrix[i][n] = h - trees[i][1] - trees[i][2];
        adjmatrix[i][n + 1] = w - trees[i][0] - trees[i][2];
        adjmatrix[i][n + 2] = trees[i][1] - trees[i][2];
        adjmatrix[i][n + 3] = trees[i][0] - trees[i][2];
        adjmatrix[n][i] = adjmatrix[i][n];
        adjmatrix[n + 1][i] = adjmatrix[i][n + 1];
        adjmatrix[n + 2][i] = adjmatrix[i][n + 2];
        adjmatrix[n + 3][i] = adjmatrix[i][n + 3];
    }

    //for (int i=0;i<8;i++) {
    //    for (int j=0;j<8;j++) {
    //        cout << setprecision(20) << adjmatrix[i][j] << ' ';
    //    }
    //    cout << '\n';
    //}


    vector<float> wall(7);
    float ne, es, sw, wn, ns, we;
    es = connection(n + 1, n + 2); sw = connection(n + 2, n + 3); we = connection(n + 1, n + 3);
    susconnection(n, n + 1, n + 2, n + 3, ne, ns, wn);
    wall[1] = sw; wall[2] = es; wall[3] = ne; wall[4] = wn; wall[5] = ns; wall[6] = we;


    //for (int i=1;i<7;i++) {
    //    cout << setprecision(20) << wall[i] << ' ';
    //} cout << '\n';


    for (int i=0;i<m;i++) {
        for (int j=1;j<5;j++) {
            if (check(visitors[i].ss, j, wall, visitors[i].ff)) cout << j;
        }
        cout << '\n';
    }
}

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