oj.uz

Submission #349384

# Submission time Handle Problem Language Result Execution time Memory
349384 2021-01-17T13:33:53 Z iANikzad Park (BOI16_park) C++14
100 / 100
 631 ms 49132 KB 
#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.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 47596 KB Output is correct
2 Correct 382 ms 47600 KB Output is correct
3 Correct 386 ms 47744 KB Output is correct
4 Correct 381 ms 47596 KB Output is correct
5 Correct 394 ms 47596 KB Output is correct
6 Correct 380 ms 47596 KB Output is correct
7 Correct 310 ms 47852 KB Output is correct
8 Correct 309 ms 47596 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 1260 KB Output is correct
2 Correct 247 ms 2444 KB Output is correct
3 Correct 251 ms 2284 KB Output is correct
4 Correct 246 ms 2284 KB Output is correct
5 Correct 246 ms 2412 KB Output is correct
6 Correct 258 ms 2540 KB Output is correct
7 Correct 242 ms 1900 KB Output is correct
8 Correct 243 ms 1900 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 47596 KB Output is correct
2 Correct 382 ms 47600 KB Output is correct
3 Correct 386 ms 47744 KB Output is correct
4 Correct 381 ms 47596 KB Output is correct
5 Correct 394 ms 47596 KB Output is correct
6 Correct 380 ms 47596 KB Output is correct
7 Correct 310 ms 47852 KB Output is correct
8 Correct 309 ms 47596 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 254 ms 1260 KB Output is correct
12 Correct 247 ms 2444 KB Output is correct
13 Correct 251 ms 2284 KB Output is correct
14 Correct 246 ms 2284 KB Output is correct
15 Correct 246 ms 2412 KB Output is correct
16 Correct 258 ms 2540 KB Output is correct
17 Correct 242 ms 1900 KB Output is correct
18 Correct 243 ms 1900 KB Output is correct
19 Correct 625 ms 49004 KB Output is correct
20 Correct 622 ms 49004 KB Output is correct
21 Correct 631 ms 48988 KB Output is correct
22 Correct 625 ms 48876 KB Output is correct
23 Correct 631 ms 49132 KB Output is correct
24 Correct 569 ms 49004 KB Output is correct