Submission #349384

#	Time	Username	Problem	Language	Result	Execution time	Memory
349384		iANikzad	Park (BOI16_park)	C++14	100 / 100	631 ms	49132 KiB

park

#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define F first
#define S second
#define debug(x) cerr<<#x<<" :"<<x<<"\n"
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define FAST ios_base::sync_with_stdio(false), cin.tie(), cout.tie();
#define int long long

typedef long long ll;
typedef long double ld;

const int maxn = 2e3 + 7;
const int mod = 1e9 + 7;
const int INF = 1e9 + 7;
const int mlog = 20;
const int SQ = 400;

int n, m, w, h;

int cnt = 0;
int ans12 = -1, ans13 = -1, ans14 = -1, ans23 = -1, ans24 = -1, ans34 = -1;

pair<int, pii> Edges[maxn * maxn];

int x[maxn], y[maxn], r[maxn];

int f[maxn];

void calc(int &x, int d) {if(x == -1) x = d;}

int get(int v) {return (f[v] == v ? v : f[v] = get(f[v]));}
void merge(int u,int v) {f[get(u)] = get(v);}

int SQR(int d) { int d2 = ceil(sqrt(d)); if(d2 * d2 == d) { return d2 + 1; } return d2; }

int32_t main()
{
    FAST;

    for(int i=0;i<maxn;i++) f[i] = i;

    cin >> n >> m >> w >> h;

    Edges[cnt++] = {w, {n+2, n+4}};
    Edges[cnt++] = {h, {n+1, n+3}};

    for(int i=1;i<=n;i++)
    {
        cin >> x[i] >> y[i] >> r[i];

        Edges[cnt++] = {(y[i] - r[i]), {i, n+1}};
        Edges[cnt++] = {(w - x[i] - r[i]), {i, n+2}};
        Edges[cnt++] = {(h - y[i] - r[i]), {i, n+3}};
        Edges[cnt++] = {(x[i] - r[i]), {i, n+4}};
    }

    for(int i=1;i<=n;i++)
    {
        for(int j = i+1;j <= n;j++)
        {
            int dx = x[i] - x[j];
            int dy = y[i] - y[j];
            int dis = dx*dx + dy*dy;
            Edges[cnt++] = {(SQR(dis) - r[i] - r[j]), {i, j}};
        }
    }

    sort(Edges, Edges+cnt);

    for(int i=0;i<cnt;i++)
    {
        int x = Edges[i].S.F;
        int y = Edges[i].S.S;
        int d = Edges[i].F;

        merge(x, y);

        if(get(n+1) == get(n+2))
        {
            calc(ans12, d);
            calc(ans24, d);
            calc(ans23, d);
        }

        if(get(n+1) == get(n+3))
        {
            calc(ans12, d);
            calc(ans13, d);
            calc(ans24, d);
            calc(ans34, d);
        }

        if(get(n+1) == get(n+4))
        {
            calc(ans12, d);
            calc(ans13, d);
            calc(ans14, d);
        }

        if(get(n+2) == get(n+3))
        {
            calc(ans13, d);
            calc(ans23, d);
            calc(ans34, d);
        }

        if(get(n+2) == get(n+4))
        {
            calc(ans13, d);
            calc(ans23, d);
            calc(ans14, d);
            calc(ans24, d);
        }

        if(get(n+3) == get(n+4))
        {
            calc(ans14, d);
            calc(ans24, d);
            calc(ans34, d);
        }
    }

    while(m--)
    {
        int r, s;
        cin >> r >> s;
        r = r*2;

        if(s == 1)
        {
            cout << "1";
            if(r < ans12) cout << "2";
            if(r < ans13) cout << "3";
            if(r < ans14) cout << "4";
        }

        if(s == 2)
        {
            if(r < ans12) cout << "1";
            cout << "2";
            if(r < ans23) cout << "3";
            if(r < ans24) cout << "4";
        }

        if(s == 3)
        {
            if(r < ans13) cout << "1";
            if(r < ans23) cout << "2";
            cout << "3";
            if(r < ans34) cout << "4";
        }

        if(s == 4)
        {
            if(r < ans14) cout << "1";
            if(r < ans24) cout << "2";
            if(r < ans34) cout << "3";
            cout << "4";
        }

        cout << "\n";
    }
  
  	return 0;
}

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