oj.uz

Submission #702994

# Submission time Handle Problem Language Result Execution time Memory
702994 2023-02-25T12:16:50 Z Hanksburger Park (BOI16_park) C++17
100 / 100
 353 ms 50884 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<pair<double, pair<ll, ll> > > vec;
ll x[2005], y[2005], r[2005], par[4005];
pair<pair<ll, ll>, ll> a[100005];
bool ans[100005][5];
ll p(ll u)
{
    return par[u]==u?u:(par[u]=p(par[u]));
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n, m, w, h, ind=0;
    cin >> n >> m >> w >> h;
    for (ll i=1; i<=n; i++)
    {
        cin >> x[i] >> y[i] >> r[i];
        for (ll j=1; j<i; j++)
            vec.push_back({sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))-r[i]-r[j], {i, j}});
        vec.push_back({x[i]-r[i], {i, n*2}});
        vec.push_back({y[i]-r[i], {i, n*2+1}});
        vec.push_back({w-x[i]-r[i], {i, n*2+2}});
        vec.push_back({h-y[i]-r[i], {i, n*2+3}});
    }
    for (ll i=1; i<=m; i++)
    {
        cin >> a[i].first.first >> a[i].first.second;
        a[i].second=i;
    }
    sort(vec.begin(), vec.end());
    sort(a+1, a+m+1);
    n*=2;
    for (ll i=1; i<=n+3; i++)
        par[i]=i;
    for (ll i=1; i<=m; i++)
    {
        while (ind<vec.size() && vec[ind].first<a[i].first.first*2)
        {
            par[p(vec[ind].second.first)]=p(vec[ind].second.second);
            ind++;
        }
        ll b=a[i].first.second-1, c=a[i].second;
        ans[c][b]=1;
        ans[c][(b+3)%4]=(p(n+b)!=p(n+(b+1)%4) && p(n+b)!=p(n+(b+2)%4) && p(n+b)!=p(n+(b+3)%4));
        ans[c][(b+1)%4]=(p(n+(b+1)%4)!=p(n+b) && p(n+(b+1)%4)!=p(n+(b+2)%4) && p(n+(b+1)%4)!=p(n+(b+3)%4));
        ans[c][(b+2)%4]=(p(n+(b+1)%4)!=p(n+b) && p(n+(b+1)%4)!=p(n+(b+3)%4) && p(n+(b+2)%4)!=p(n+b) && p(n+(b+2)%4)!=p(n+(b+3)%4));
    }
    for (ll i=1; i<=m; i++)
    {
        for (ll j=0; j<=3; j++)
            if (ans[i][j])
                cout << j+1;
        cout << '\n';
    }
}

Compilation message

park.cpp: In function 'int main()':
park.cpp:41:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<double, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         while (ind<vec.size() && vec[ind].first<a[i].first.first*2)
      |                ~~~^~~~~~~~~~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 49660 KB Output is correct
2 Correct 283 ms 49696 KB Output is correct
3 Correct 294 ms 49756 KB Output is correct
4 Correct 285 ms 49668 KB Output is correct
5 Correct 287 ms 49688 KB Output is correct
6 Correct 292 ms 49692 KB Output is correct
7 Correct 288 ms 49664 KB Output is correct
8 Correct 272 ms 49700 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 4172 KB Output is correct
2 Correct 39 ms 4048 KB Output is correct
3 Correct 39 ms 4088 KB Output is correct
4 Correct 40 ms 4076 KB Output is correct
5 Correct 41 ms 4036 KB Output is correct
6 Correct 42 ms 4188 KB Output is correct
7 Correct 35 ms 3472 KB Output is correct
8 Correct 36 ms 3408 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 49660 KB Output is correct
2 Correct 283 ms 49696 KB Output is correct
3 Correct 294 ms 49756 KB Output is correct
4 Correct 285 ms 49668 KB Output is correct
5 Correct 287 ms 49688 KB Output is correct
6 Correct 292 ms 49692 KB Output is correct
7 Correct 288 ms 49664 KB Output is correct
8 Correct 272 ms 49700 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 42 ms 4172 KB Output is correct
12 Correct 39 ms 4048 KB Output is correct
13 Correct 39 ms 4088 KB Output is correct
14 Correct 40 ms 4076 KB Output is correct
15 Correct 41 ms 4036 KB Output is correct
16 Correct 42 ms 4188 KB Output is correct
17 Correct 35 ms 3472 KB Output is correct
18 Correct 36 ms 3408 KB Output is correct
19 Correct 333 ms 50748 KB Output is correct
20 Correct 326 ms 50752 KB Output is correct
21 Correct 327 ms 50880 KB Output is correct
22 Correct 337 ms 50680 KB Output is correct
23 Correct 353 ms 50708 KB Output is correct
24 Correct 328 ms 50884 KB Output is correct