oj.uz

Submission #935734

# Submission time Handle Problem Language Result Execution time Memory
935734 2024-02-29T12:51:33 Z Neco_arc Park (BOI16_park) C++17
100 / 100
 323 ms 53940 KB 
#include <bits/stdc++.h>

#define ll long long
#define ull unsigned long long
#define all(x) x.begin(), x.end()
#define Neco "Park"
#define resp(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define getbit(x,i) ((x >> i)&1)
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define cntbit(x) __builtin_popcountll(x)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define maxn (int) 2e5 + 7
#define int long long

using namespace std;

const ll mod = 1e9 + 7; //972663749
const ll base = 911382323;
const pair<int, int> sth[] = {{1, 2}, {2, 3}, {3, 4}, {1, 4}, {1, 3}, {2, 4}};

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll GetRandom(ll l, ll r)
{
    return uniform_int_distribution<ll> (l, r)(rng);
}

int n, q, W, H;
int ans[5][5];
tuple<int, int, int> circle[maxn];
struct dl {int x, y, w; };
vector<dl> E;

vector<pair<int, int>> Case[6];
void init() {
    Case[0] = {{1, 4}, {1, 3}, {1, 2}};
    Case[1] = {{2, 1}, {2, 4}, {2, 3}};
    Case[2] = {{3, 2}, {3, 1}, {3, 4}};
    Case[3] = {{4, 3}, {4, 2}, {4, 1}};
    Case[4] = {{1, 3}, {2, 4}, {1, 4}, {2, 3}};
    Case[5] = {{1, 3}, {2, 4}, {1, 2}, {3, 4}};
}


struct DSU {
    int lab[maxn];

    void init(int N) {
        fi(i, 1, N) lab[i] = -1;
    }

    int get_rt(int u) { return lab[u] < 0 ? u : lab[u] = get_rt(lab[u]); }

    void uni(int u, int v) {
        int p = get_rt(u), q = get_rt(v); if(p == q) return;
        if(lab[p] > lab[q]) swap(p, q);
        lab[p] += lab[q], lab[q] = p;
    }
} dsu;

ll calc(ll x, ll y) {
    return sqrt(x * x + y * y);
}

void solve()
{

    cin >> n >> q >> W >> H;
    dsu.init(n + 4), init();

    fi(i, 1, n) {
        int x, y, r;
        cin >> x >> y >> r;

        E.push_back({n + 1, i, y - r});
        E.push_back({n + 2, i, W - x - r});
        E.push_back({n + 3, i, H - y - r});
        E.push_back({n + 4, i, x - r});

        circle[i] = {x, y, r};
    }

    fi(i, 1, n - 1) fi(j, i + 1, n)
    {
        int u, v, r1, x, y, r2;
        tie(u, v, r1) = circle[i], tie(x, y, r2) = circle[j];
        E.push_back({i, j, calc(x - u, y - v) - r1 - r2});
    }

    memset(ans, 60, sizeof ans);
    sort(all(E), [](dl x, dl y){
            return x.w < y.w;
         } );

    for(dl p : E)
    {
        dsu.uni(p.x, p.y);
        int u, v;
        fi(i, 0, 5) {
            tie(u, v) = sth[i];
            for(auto [x, y] : Case[i]) {
                if(dsu.get_rt(n + x) == dsu.get_rt(n + y) && ans[u][v] >= 1e9) ans[u][v] = ans[v][u] = p.w;
            }
        }
    }

    fi(_, 1, q) {
        int x, r;
        cin >> r >> x, r *= 2;

        fi(i, 1, 4) if(ans[x][i] >= r) cout << i;
        cout << '\n';
    }


}


main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if(fopen(Neco".inp", "r")) {
        freopen(Neco".inp", "r", stdin);
        freopen(Neco".out", "w", stdout);
    }


    int nTest = 1;
//    cin >> nTest;


    while(nTest--)
    {
        solve();
    }


    return 0;
}

Compilation message

park.cpp:121:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  121 | main()
      | ^~~~
park.cpp: In function 'int main()':
park.cpp:129:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |         freopen(Neco".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:130:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |         freopen(Neco".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 51896 KB Output is correct
2 Correct 290 ms 51896 KB Output is correct
3 Correct 300 ms 52652 KB Output is correct
4 Correct 294 ms 52384 KB Output is correct
5 Correct 297 ms 53444 KB Output is correct
6 Correct 287 ms 52924 KB Output is correct
7 Correct 263 ms 52920 KB Output is correct
8 Correct 304 ms 53116 KB Output is correct
9 Correct 1 ms 2592 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 4312 KB Output is correct
2 Correct 25 ms 4304 KB Output is correct
3 Correct 24 ms 4300 KB Output is correct
4 Correct 25 ms 4300 KB Output is correct
5 Correct 24 ms 4312 KB Output is correct
6 Correct 26 ms 4568 KB Output is correct
7 Correct 21 ms 3924 KB Output is correct
8 Correct 21 ms 3932 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 51896 KB Output is correct
2 Correct 290 ms 51896 KB Output is correct
3 Correct 300 ms 52652 KB Output is correct
4 Correct 294 ms 52384 KB Output is correct
5 Correct 297 ms 53444 KB Output is correct
6 Correct 287 ms 52924 KB Output is correct
7 Correct 263 ms 52920 KB Output is correct
8 Correct 304 ms 53116 KB Output is correct
9 Correct 1 ms 2592 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 26 ms 4312 KB Output is correct
12 Correct 25 ms 4304 KB Output is correct
13 Correct 24 ms 4300 KB Output is correct
14 Correct 25 ms 4300 KB Output is correct
15 Correct 24 ms 4312 KB Output is correct
16 Correct 26 ms 4568 KB Output is correct
17 Correct 21 ms 3924 KB Output is correct
18 Correct 21 ms 3932 KB Output is correct
19 Correct 312 ms 53444 KB Output is correct
20 Correct 314 ms 52460 KB Output is correct
21 Correct 323 ms 53940 KB Output is correct
22 Correct 316 ms 53180 KB Output is correct
23 Correct 319 ms 51984 KB Output is correct
24 Correct 297 ms 52148 KB Output is correct