Submission #645637

#	Time	Username	Problem	Language	Result	Execution time	Memory
645637		Alexandruabcde	Park (BOI16_park)	C++14	0 / 100	442 ms	69548 KiB

park

#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, {i, N+1}});
        E.push_back({H - T[i].y, {i, N+2}});
        E.push_back({W - T[i].x, {i, N+3}});
        E.push_back({T[i].y, {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;
}

/*
5 3
16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 1
2 2
2 1
*/

Compilation message (stderr)

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
• Subtask 2: 0 / 31
• Subtask 3: 0 / 42