oj.uz

Submission #645653

# Submission time Handle Problem Language Result Execution time Memory
645653 2022-09-27T15:20:55 Z Alexandruabcde Park (BOI16_park) C++14
100 / 100
 514 ms 71128 KB 
#include <bits/stdc++.h>

using namespace std;

constexpr int NMAX = 2010;
constexpr int MMAX = 1e5 + 2;
typedef long double LD;
typedef pair <LD, pair <int, int> > PLDII;
typedef pair <int, int> PII;

struct Tree {
    LD x, y;
    LD rad;
};

struct Query {
    LD rad;
    int ind;
    int corner;

    bool operator < (const Query &other) const {
        return rad < other.rad;
    }
};

Query Q[MMAX];

Tree T[NMAX];
LD W, H;
int N, M;
vector <PLDII> E;

LD Distance (Tree a, Tree b) {
    LD dist = sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));

    return dist - a.rad - b.rad;
}

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;

    cin >> W >> H;

    for (int i = 1; i <= N; ++ i )
        cin >> T[i].x >> T[i].y >> T[i].rad;
}

vector <PII> Need[5][5];

void Precompute () {
    for (int i = 1; i <= N; ++ i ) {
        for (int j = i+1; j <= N; ++ j ) {
            LD d = Distance(T[i], T[j]);

            E.push_back({d, {i, j}});
        }

        E.push_back({T[i].x - T[i].rad, {i, N+1}});
        E.push_back({H - T[i].y - T[i].rad, {i, N+2}});
        E.push_back({W - T[i].x - T[i].rad, {i, N+3}});
        E.push_back({T[i].y - T[i].rad, {i, N+4}});
    }

    sort(E.begin(), E.end());

    for (int i = 1; i <= M; ++ i ) {
        cin >> Q[i].rad >> Q[i].corner;

        Q[i].ind = i;
    }

    sort(Q + 1, Q + M + 1);

    Need[1][2].push_back({N+4, N+1});
    Need[1][2].push_back({N+4, N+2});
    Need[1][2].push_back({N+4, N+3});

    Need[1][3].push_back({N+4, N+1});
    Need[1][3].push_back({N+4, N+2});
    Need[1][3].push_back({N+1, N+3});
    Need[1][3].push_back({N+2, N+3});

    Need[1][4].push_back({N+1, N+2});
    Need[1][4].push_back({N+1, N+3});
    Need[1][4].push_back({N+1, N+4});

    Need[2][3].push_back({N+3, N+2});
    Need[2][3].push_back({N+3, N+1});
    Need[2][3].push_back({N+3, N+4});

    Need[2][4].push_back({N+1, N+2});
    Need[2][4].push_back({N+1, N+3});
    Need[2][4].push_back({N+2, N+4});
    Need[2][4].push_back({N+3, N+4});

    Need[3][4].push_back({N+2, N+1});
    Need[3][4].push_back({N+2, N+3});
    Need[3][4].push_back({N+2, N+4});
}

string ans[MMAX];

int Dad[NMAX];
int Sz[NMAX];

int Reprezentant (int Node) {
    if (Dad[Node] == Node) return Node;

    Dad[Node] = Reprezentant(Dad[Node]);

    return Dad[Node];
}

void Unify (int x, int y) {
    x = Reprezentant(x);
    y = Reprezentant(y);

    if (x == y) return;

    if (Sz[x] <= Sz[y]) {
        Dad[x] = y;
        Sz[y] += Sz[x];
    }
    else {
        Dad[y] = x;
        Sz[x] += Sz[y];
    }
}

bool Connected (int x, int y) {
    return (Reprezentant(x) == Reprezentant(y));
}

bool Can (int from, int to) {
    if (from == to) return true;

    int st = min(from, to);
    int dr = max(from, to);

    for (auto it : Need[st][dr]) {
        if (Connected(it.first, it.second)) return false;
    }

    return true;
}

void Solve () {
    int index = 0;

    for (int i = 1; i <= N + 4; ++ i ) {
        Dad[i] = i;
        Sz[i] = 1;
    }

    for (int i = 1; i <= M; ++ i ) {
        while (index < E.size() && E[index].first < 2 * Q[i].rad) {
            Unify(E[index].second.first, E[index].second.second);

            int x = E[index].second.first;
            int y = E[index].second.second;
            LD d = E[index].first;
            ++ index;
        }

        for (int j = 1; j <= 4; ++ j )
            if (Can(Q[i].corner, j)) ans[Q[i].ind].push_back('0' + j);
    }

    for (int i = 1; i <= M; ++ i )
        cout << ans[i] << '\n';
}

int main () {
    Read();

    Precompute();

    Solve();

    return 0;
}

Compilation message

park.cpp: In function 'void Solve()':
park.cpp:159:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long double, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |         while (index < E.size() && E[index].first < 2 * Q[i].rad) {
      |                ~~~~~~^~~~~~~~~~
park.cpp:162:17: warning: unused variable 'x' [-Wunused-variable]
  162 |             int x = E[index].second.first;
      |                 ^
park.cpp:163:17: warning: unused variable 'y' [-Wunused-variable]
  163 |             int y = E[index].second.second;
      |                 ^
park.cpp:164:16: warning: unused variable 'd' [-Wunused-variable]
  164 |             LD d = E[index].first;
      |                ^

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 432 ms 69268 KB Output is correct
2 Correct 443 ms 69304 KB Output is correct
3 Correct 430 ms 69336 KB Output is correct
4 Correct 445 ms 69240 KB Output is correct
5 Correct 433 ms 69324 KB Output is correct
6 Correct 428 ms 69396 KB Output is correct
7 Correct 420 ms 69396 KB Output is correct
8 Correct 404 ms 69244 KB Output is correct
9 Correct 2 ms 3412 KB Output is correct
10 Correct 3 ms 3412 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 7652 KB Output is correct
2 Correct 63 ms 7724 KB Output is correct
3 Correct 64 ms 7664 KB Output is correct
4 Correct 68 ms 7640 KB Output is correct
5 Correct 68 ms 7788 KB Output is correct
6 Correct 65 ms 8832 KB Output is correct
7 Correct 71 ms 7984 KB Output is correct
8 Correct 58 ms 8032 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 432 ms 69268 KB Output is correct
2 Correct 443 ms 69304 KB Output is correct
3 Correct 430 ms 69336 KB Output is correct
4 Correct 445 ms 69240 KB Output is correct
5 Correct 433 ms 69324 KB Output is correct
6 Correct 428 ms 69396 KB Output is correct
7 Correct 420 ms 69396 KB Output is correct
8 Correct 404 ms 69244 KB Output is correct
9 Correct 2 ms 3412 KB Output is correct
10 Correct 3 ms 3412 KB Output is correct
11 Correct 68 ms 7652 KB Output is correct
12 Correct 63 ms 7724 KB Output is correct
13 Correct 64 ms 7664 KB Output is correct
14 Correct 68 ms 7640 KB Output is correct
15 Correct 68 ms 7788 KB Output is correct
16 Correct 65 ms 8832 KB Output is correct
17 Correct 71 ms 7984 KB Output is correct
18 Correct 58 ms 8032 KB Output is correct
19 Correct 514 ms 71032 KB Output is correct
20 Correct 492 ms 71004 KB Output is correct
21 Correct 489 ms 71128 KB Output is correct
22 Correct 489 ms 71084 KB Output is correct
23 Correct 471 ms 70952 KB Output is correct
24 Correct 473 ms 71008 KB Output is correct