oj.uz

Submission #999428

# Submission time Handle Problem Language Result Execution time Memory
999428 2024-06-15T13:20:29 Z vyshniak_n Park (BOI16_park) C++17
100 / 100
 309 ms 51900 KB 
//#pragma optimize("Ofast")
//#pragma optimize("unroll-loops")
//#pragma traget("avx,avx2")
 
#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
#define el '\n'
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define point pair <ll, ll>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
 
using namespace std;
 
#include <random>
mt19937 rnd(time(0));
 
const ll INF = 1e18 + 10;
const ll inf = 1e9 + 10;
const ll N = 2e3 + 10;
const ll mod = 998244353;
const ll LOG = 22;
const ll K = 1e3 + 20;

ll x[N], y[N], r[N];
ll parent[N], sz[N];
void build(ll n) {
    for (ll i = 1; i <= n; i++)
        parent[i] = i, sz[i] = 1;
}
ll lead(ll v) {
    if (parent[v] == v)
        return v;
    return parent[v] = lead(parent[v]);
}
void union_sets(ll a, ll b) {
    a = lead(a);
    b = lead(b);

    if (a != b) {
        if (sz[a] < sz[b])
            swap(a, b);

        sz[a] += sz[b];
        parent[b] = a;
    }
}

void solve() {
    ll n, m, w, h;
    cin >> n >> m >> w >> h;

    vector <pair <ll, pair <ll, ll>>> edges;
    for (ll i = 1; i <= n; i++) {
        cin >> x[i] >> y[i] >> r[i];

        for (ll j = 1; j < i; j++) {
            ll distance = abs(x[i] - x[j]) * abs(x[i] - x[j]) +
                          abs(y[i] - y[j]) * abs(y[i] - y[j]);

            distance = sqrtl(distance) - r[i] - r[j];
            edges.pb({distance, {i, j}});       
        }

        edges.pb({x[i] - r[i], {i, n + 1}});
        edges.pb({y[i] - r[i], {i, n + 2}});
        edges.pb({w - x[i] - r[i], {i, n + 3}});
        edges.pb({h - y[i] - r[i], {i, n + 4}});
    }

    sort(all(edges));
    build(n + 4);

    ll mx[5][5];
    for (ll i = 1; i <= 4; i++)
        for (ll j = 1; j <= 4; j++)
            mx[i][j] = inf;

    for (ll i = 0; i < edges.size(); i++) {
        union_sets(edges[i].ss.ff, edges[i].ss.ss);

        for (ll j = 1; j <= 4; j++)
            for (ll k = 1; k <= 4; k++)
                if (lead(n + j) == lead(n + k))
                    mx[j][k] = min(mx[j][k], edges[i].ff);
    }

    while (m--) {
        ll rad, e;
        cin >> rad >> e;

        ll d = 2 * rad;

        if (e == 1) {
            if (d > mx[1][2])
                cout << 1 << el;
            else if (d > mx[1][3])
                cout << 12 << el;
            else if (d > mx[2][3] && d > mx[1][4])
                cout << 13 << el;
            else if (d > mx[2][4])
                cout << 14 << el;
            else if (d > mx[2][3])
                cout << 134 << el;
            else if (d > mx[3][4])
                cout << 124 << el;
            else if (d > mx[1][4])
                cout << 123 << el;
            else
                cout << 1234 << el;
        } else if (e == 2) {
            if (d > mx[2][3])
                cout << 2 << el;
            else if (d > mx[1][3])
                cout << 12 << el;
            else if (d > mx[1][2] && d > mx[3][4])
                cout << 24 << el;
            else if (d > mx[2][4])
                cout << 23 << el;
            else if (d > mx[1][2])
                cout << 234 << el;
            else if (d > mx[3][4])
                cout << 124 << el;
            else if (d > mx[1][4])
                cout << 123 << el;
            else
                cout << 1234 << el;
        } else if (e == 3) {
            if (d > mx[3][4])
                cout << 3 << el;
            else if (d > mx[1][3])
                cout << 34 << el;
            else if (d > mx[2][3] && d > mx[1][4])
                cout << 13 << el;
            else if (d > mx[2][4])
                cout << 23 << el;
            else if (d > mx[1][2])
                cout << 234 << el;
            else if (d > mx[2][3])
                cout << 134 << el;
            else if (d > mx[1][4])
                cout << 123 << el;
            else
                cout << 1234 << el;
        } else {
            if (d > mx[4][1])
                cout << 4 << el;
            else if (d > mx[1][3])
                cout << 34 << el;
            else if (d > mx[1][2] && d > mx[3][4])
                cout << 24 << el;
            else if (d > mx[2][4])
                cout << 14 << el;
            else if (d > mx[1][2])
                cout << 234 << el;
            else if (d > mx[2][3])
                cout << 134 << el;
            else if (d > mx[3][4])
                cout << 124 << el;
            else
                cout << 1234 << el;
        }
    }
    return;
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    int tests = 1;
    //cin >> tests;
 
    while (tests--) 
        solve();
    return 0;
}
/*
5 1
16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 1
*/

Compilation message

park.cpp: In function 'void solve()':
park.cpp:117:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |     for (ll i = 0; i < edges.size(); i++) {
      |                    ~~^~~~~~~~~~~~~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 50880 KB Output is correct
2 Correct 267 ms 51780 KB Output is correct
3 Correct 275 ms 50880 KB Output is correct
4 Correct 265 ms 51644 KB Output is correct
5 Correct 268 ms 50796 KB Output is correct
6 Correct 261 ms 51644 KB Output is correct
7 Correct 237 ms 51128 KB Output is correct
8 Correct 249 ms 51380 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1432 KB Output is correct
2 Correct 20 ms 2372 KB Output is correct
3 Correct 20 ms 2260 KB Output is correct
4 Correct 20 ms 2468 KB Output is correct
5 Correct 26 ms 2476 KB Output is correct
6 Correct 18 ms 2516 KB Output is correct
7 Correct 18 ms 1884 KB Output is correct
8 Correct 16 ms 1948 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 50880 KB Output is correct
2 Correct 267 ms 51780 KB Output is correct
3 Correct 275 ms 50880 KB Output is correct
4 Correct 265 ms 51644 KB Output is correct
5 Correct 268 ms 50796 KB Output is correct
6 Correct 261 ms 51644 KB Output is correct
7 Correct 237 ms 51128 KB Output is correct
8 Correct 249 ms 51380 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 18 ms 1432 KB Output is correct
12 Correct 20 ms 2372 KB Output is correct
13 Correct 20 ms 2260 KB Output is correct
14 Correct 20 ms 2468 KB Output is correct
15 Correct 26 ms 2476 KB Output is correct
16 Correct 18 ms 2516 KB Output is correct
17 Correct 18 ms 1884 KB Output is correct
18 Correct 16 ms 1948 KB Output is correct
19 Correct 307 ms 51900 KB Output is correct
20 Correct 283 ms 50864 KB Output is correct
21 Correct 309 ms 51632 KB Output is correct
22 Correct 275 ms 51900 KB Output is correct
23 Correct 281 ms 51872 KB Output is correct
24 Correct 248 ms 49840 KB Output is correct