제출 #877836

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
877836		Hamed_Ghaffari	Park (BOI16_park)	C++17	100 / 100	506 ms	68284 KiB

park

#include <bits/stdc++.h>
using namespace std;
#define int ll
#define double long double

typedef long long       ll;
typedef pair<int, int>  pii;

#define FastIO          cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
#define FileIO          freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define F               first
#define S               second
#define max_heap(T)     priority_queue<T>
#define min_heap(T)     priority_queue<T, vector<T>, greater<T>>
#define fr(i,a,b)       for(int i=a;i<b;i++)
#define frr(i,a,b)      for(int i=a;i>b;i--)
#define frin(i,A)       for(auto &i : A)
#define frp(a,b,A)      for(auto [a, b] : A)
#define SZ(x)           (int)x.size()
#define all(A)          A.begin(), A.end()
#define mins(a,b)       a = min(a,b)
#define maxs(a,b)       a = max(a,b)
#define pb              push_back
#define kill(x)         cout << x << '\n', exit(0)
#define md(a)           (a%MOD+MOD)%MOD

const ll  INF  = 4e18;
const ll  MOD  = 1e9 + 7;
const int MAXN = 2008;
const int LOG  = 30;

double dis(pii p1, pii p2) {
    double x = p1.F-p2.F, y = p1.S-p2.S;
    return sqrt(x*x + y*y);
}

int w, h, n, m;
struct circle { int x, y, r; } C[MAXN];
struct edge { 
    int u, v;
    double w;
    edge() {}
    edge(int u_, int v_, double w_) {
        u = u_, v = v_, w = w_;
    }
    bool operator < (const edge &e) const {
        return w < e.w;
    }
};
vector<edge> E;
struct DSU {
    int par[MAXN], sz[MAXN];
    void clear() {
        fr(i, 0, MAXN)
            par[i] = i,
            sz[i] = 1;
    }
    int Find(int v) {
        return v == par[v] ? v : par[v] = Find(par[v]);
    }
    bool Union(int u, int v) {
        if((u = Find(u)) == (v = Find(v)))
            return 0;
        if(sz[u] < sz[v])
            swap(u, v);
        par[v] = u;
        sz[u] += sz[v];
        return 1;
    }
} dsu;
double fir[5][5];

void solve() {
    cin >> n >> m;
    cin >> w >> h;
    fr(i, 1, n+1) {
        cin >> C[i].x >> C[i].y >> C[i].r;
        E.pb({i, n+1, 1.0*(h-(C[i].y+C[i].r))});
        E.pb({i, n+2, 1.0*(w-(C[i].x+C[i].r))});
        E.pb({i, n+3, 1.0*(C[i].y-C[i].r)});
        E.pb({i, n+4, 1.0*(C[i].x-C[i].r)});
    }
    fr(i, 1, n+1)
        fr(j, i+1, n+1)
            E.pb({i, j, dis({C[i].x, C[i].y}, {C[j].x, C[j].y})-C[i].r-C[j].r});
    sort(all(E));
    dsu.clear();
    fr(i, 1, 5)
        fr(j, 1, 5)
            fir[i][j] = INF;
    frin(e, E) {
        dsu.Union(e.u, e.v);
        fr(i, 1, 5)
            fr(j, 1, 5)
                if(i != j && dsu.Find(n+i) == dsu.Find(n+j))
                    mins(fir[i][j], e.w);
    }
    while(m--) {
        ll r;
        int e;
        cin >> r >> e;
        r *= 2;
        if(e == 1) {
            cout << 1;
            if(min({fir[1][3], fir[2][3], fir[3][4]}) >= r) cout << 2;
            if(min({fir[1][3], fir[2][4], fir[3][4], fir[1][2]}) >= r) cout << 3;
            if(min({fir[2][4], fir[1][4], fir[3][4]}) >= r) cout << 4;
        }
        if(e == 2) {
            if(min({fir[1][3], fir[2][3], fir[3][4]}) >= r) cout << 1;
            cout << 2;
            if(min({fir[2][4], fir[1][2], fir[2][3]}) >= r) cout << 3;
            if(min({fir[1][3], fir[2][4], fir[2][3], fir[1][4]}) >= r) cout << 4;
        }
        if(e == 3) {
            if(min({fir[1][3], fir[2][4], fir[3][4], fir[1][2]}) >= r) cout << 1;
            if(min({fir[2][4], fir[1][2], fir[2][3]}) >= r) cout << 2;
            cout << 3;
            if(min({fir[1][2], fir[1][4], fir[1][3]}) >= r) cout << 4;
        }
        if(e == 4) {
            if(min({fir[2][4], fir[1][4], fir[3][4]}) >= r) cout << 1;
            if(min({fir[1][3], fir[2][4], fir[2][3], fir[1][4]}) >= r) cout << 2;
            if(min({fir[1][2], fir[1][4], fir[1][3]}) >= r) cout << 3;
            cout << 4;
        }
        cout << '\n';
    }
}

int32_t main() {
    FastIO
    int T = 1;
    // cin >> T;
    while(T--)
        solve();
    return 0;
}

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