oj.uz

Submission #702992

# Submission time Handle Problem Language Result Execution time Memory
702992 2023-02-25T12:14:41 Z Hanksburger Park (BOI16_park) C++17
100 / 100
 520 ms 67648 KB 
#include <bits/stdc++.h>
using namespace std;
vector<pair<long double, pair<long long, long long> > > vec;
long long x[2005], y[2005], r[2005], par[4005];
pair<pair<long long, long long>, long long> a[100005];
bool ans[100005][5];
long long p(long long u)
{
    return par[u]==u?u:(par[u]=p(par[u]));
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n, m, w, h, ind=0;
    cin >> n >> m >> w >> h;
    for (long long i=1; i<=n; i++)
    {
        cin >> x[i] >> y[i] >> r[i];
        for (long long 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 (long long 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 (long long i=1; i<=n+3; i++)
        par[i]=i;
    for (long long 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++;
        }
        long long 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 (long long i=1; i<=m; i++)
    {
        for (long long j=0; j<=3; j++)
            if (ans[i][j])
                cout << j+1;
        cout << '\n';
    }
}

Compilation message

park.cpp: In function 'int main()':
park.cpp:40:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long double, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         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 419 ms 66072 KB Output is correct
2 Correct 421 ms 66164 KB Output is correct
3 Correct 425 ms 66164 KB Output is correct
4 Correct 432 ms 66164 KB Output is correct
5 Correct 457 ms 66148 KB Output is correct
6 Correct 415 ms 66172 KB Output is correct
7 Correct 435 ms 66108 KB Output is correct
8 Correct 400 ms 66208 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 4284 KB Output is correct
2 Correct 42 ms 5280 KB Output is correct
3 Correct 40 ms 5248 KB Output is correct
4 Correct 46 ms 5304 KB Output is correct
5 Correct 44 ms 5316 KB Output is correct
6 Correct 44 ms 5280 KB Output is correct
7 Correct 38 ms 4620 KB Output is correct
8 Correct 39 ms 4624 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 66072 KB Output is correct
2 Correct 421 ms 66164 KB Output is correct
3 Correct 425 ms 66164 KB Output is correct
4 Correct 432 ms 66164 KB Output is correct
5 Correct 457 ms 66148 KB Output is correct
6 Correct 415 ms 66172 KB Output is correct
7 Correct 435 ms 66108 KB Output is correct
8 Correct 400 ms 66208 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 48 ms 4284 KB Output is correct
12 Correct 42 ms 5280 KB Output is correct
13 Correct 40 ms 5248 KB Output is correct
14 Correct 46 ms 5304 KB Output is correct
15 Correct 44 ms 5316 KB Output is correct
16 Correct 44 ms 5280 KB Output is correct
17 Correct 38 ms 4620 KB Output is correct
18 Correct 39 ms 4624 KB Output is correct
19 Correct 520 ms 67604 KB Output is correct
20 Correct 451 ms 67500 KB Output is correct
21 Correct 473 ms 67624 KB Output is correct
22 Correct 484 ms 67532 KB Output is correct
23 Correct 455 ms 67500 KB Output is correct
24 Correct 459 ms 67648 KB Output is correct