oj.uz

Submission #645645

# Submission time Handle Problem Language Result Execution time Memory
645645 2022-09-27T15:03:11 Z Alexandruabcde Park (BOI16_park) C++14
0 / 100
 448 ms 69508 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+2});

    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);

            ++ 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) {
      |                ~~~~~~^~~~~~~~~~

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 69376 KB Output is correct
2 Correct 425 ms 69508 KB Output is correct
3 Correct 440 ms 69340 KB Output is correct
4 Correct 441 ms 69376 KB Output is correct
5 Correct 435 ms 69328 KB Output is correct
6 Correct 448 ms 69364 KB Output is correct
7 Correct 409 ms 69408 KB Output is correct
8 Incorrect 404 ms 69456 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 7872 KB Output is correct
2 Correct 69 ms 8732 KB Output is correct
3 Correct 67 ms 8668 KB Output is correct
4 Correct 66 ms 8704 KB Output is correct
5 Incorrect 66 ms 8720 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 69376 KB Output is correct
2 Correct 425 ms 69508 KB Output is correct
3 Correct 440 ms 69340 KB Output is correct
4 Correct 441 ms 69376 KB Output is correct
5 Correct 435 ms 69328 KB Output is correct
6 Correct 448 ms 69364 KB Output is correct
7 Correct 409 ms 69408 KB Output is correct
8 Incorrect 404 ms 69456 KB Output isn't correct
9 Halted 0 ms 0 KB -