oj.uz

Submission #935299

# Submission time Handle Problem Language Result Execution time Memory
935299 2024-02-29T03:15:48 Z Sharky Park (BOI16_park) C++17
100 / 100
 244 ms 60384 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
const int N = 2010;
using ld = long double;
 
struct pr {
    int i, j, di;
    bool operator < (const pr& o) const {
        return di < o.di;
    }
};
 
vector<pr> a;
 
int x[N], y[N], r[N], p[N];
vector<bool> ans[100005];
vector<array<int, 3>> qry;
 
int find(int u) {
    return p[u] == u ? u : p[u] = find(p[u]);
}
 
void merge(int u, int v) {
    p[find(v)] = find(u);
}
 
bool same_set(int u, int v) {
    return find(u) == find(v);
}
 
int dist(int i, int j) {
    return floor(sqrt((x[j] - x[i]) * (x[j] - x[i]) + (y[j] - y[i]) * (y[j] - y[i]))) - r[i] - r[j];
}
 
int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m, w, h;
    cin >> n >> m >> w >> h;
    for (int i = 1; i <= n; i++) cin >> x[i] >> y[i] >> r[i];
    for (int i = 1; i <= n + 4; i++) p[i] = i;
    for (int i = 1; i <= m; i++) {
        int ra, e;
        cin >> ra >> e;
        qry.push_back({ra, e, i});
    }
    sort(qry.begin(), qry.end());
    for (int i = 1; i <= n; i++) for (int j = i + 1; j <= n; j++) a.push_back((pr) {i, j, dist(i, j)});
    int UP = n + 1;
    int LEFT = n + 2;
    int RIGHT = n + 3;
    int DOWN = n + 4;
    for (int i = 1; i <= n; i++) {
        a.push_back({i, UP, (h - (y[i] + r[i]))});
        a.push_back({i, LEFT, (x[i] - r[i])});
        a.push_back({i, RIGHT, (w - (x[i] + r[i]))});
        a.push_back({i, DOWN, (y[i] - r[i])});
    }
    sort(a.begin(), a.end());
    int pt = 0;
    for (auto& [ra, e, idx] : qry) {
        while (pt < a.size() && 2 * ra > a[pt].di) {
            merge(a[pt].i, a[pt].j);
            pt++;
        }
        vector<bool> can(5, 0);
        if (e == 1) {
            can[1] = 1;
            can[2] = !(same_set(UP, DOWN) || same_set(LEFT, DOWN) || same_set(RIGHT, DOWN));
            can[3] = !(same_set(LEFT, RIGHT) || same_set(LEFT, DOWN) || same_set(UP, DOWN) || same_set(UP, RIGHT));
            can[4] = !(same_set(LEFT, RIGHT) || same_set(LEFT, DOWN) || same_set(LEFT, UP));
        } else if (e == 2) {
            can[1] = !(same_set(UP, DOWN) || same_set(LEFT, DOWN) || same_set(RIGHT, DOWN));
            can[2] = 1;
            can[3] = !(same_set(RIGHT, LEFT) || same_set(RIGHT, UP) || same_set(RIGHT, DOWN));
            can[4] = !(same_set(UP, DOWN) || same_set(LEFT, RIGHT) || same_set(RIGHT, DOWN) || same_set(LEFT, UP));
        } else if (e == 3) {
            can[1] = !(same_set(LEFT, RIGHT) || same_set(LEFT, DOWN) || same_set(UP, DOWN) || same_set(UP, RIGHT));
            can[2] = !(same_set(RIGHT, LEFT) || same_set(RIGHT, UP) || same_set(RIGHT, DOWN));
            can[3] = 1;
            can[4] = !(same_set(UP, LEFT) || same_set(UP, DOWN) || same_set(UP, RIGHT));
        } else {
            can[1] = !(same_set(LEFT, RIGHT) || same_set(LEFT, DOWN) || same_set(LEFT, UP));
            can[2] = !(same_set(UP, DOWN) || same_set(LEFT, RIGHT) || same_set(RIGHT, DOWN) || same_set(LEFT, UP));
            can[3] = !(same_set(UP, LEFT) || same_set(UP, DOWN) || same_set(UP, RIGHT));
            can[4] = 1;
        }
        ans[idx] = can;
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= 4; j++) if (ans[i][j]) cout << j;
        cout << '\n';
    }
} 

/*
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

park.cpp: In function 'int32_t main()':
park.cpp:63:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<pr>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         while (pt < a.size() && 2 * ra > a[pt].di) {
      |                ~~~^~~~~~~~~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 54208 KB Output is correct
2 Correct 199 ms 54452 KB Output is correct
3 Correct 190 ms 53844 KB Output is correct
4 Correct 193 ms 54796 KB Output is correct
5 Correct 194 ms 54968 KB Output is correct
6 Correct 190 ms 55372 KB Output is correct
7 Correct 189 ms 54976 KB Output is correct
8 Correct 175 ms 54456 KB Output is correct
9 Correct 1 ms 4188 KB Output is correct
10 Correct 1 ms 4188 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 10688 KB Output is correct
2 Correct 50 ms 10684 KB Output is correct
3 Correct 66 ms 10940 KB Output is correct
4 Correct 49 ms 10600 KB Output is correct
5 Correct 48 ms 10684 KB Output is correct
6 Correct 54 ms 10688 KB Output is correct
7 Correct 46 ms 9944 KB Output is correct
8 Correct 61 ms 11172 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 54208 KB Output is correct
2 Correct 199 ms 54452 KB Output is correct
3 Correct 190 ms 53844 KB Output is correct
4 Correct 193 ms 54796 KB Output is correct
5 Correct 194 ms 54968 KB Output is correct
6 Correct 190 ms 55372 KB Output is correct
7 Correct 189 ms 54976 KB Output is correct
8 Correct 175 ms 54456 KB Output is correct
9 Correct 1 ms 4188 KB Output is correct
10 Correct 1 ms 4188 KB Output is correct
11 Correct 50 ms 10688 KB Output is correct
12 Correct 50 ms 10684 KB Output is correct
13 Correct 66 ms 10940 KB Output is correct
14 Correct 49 ms 10600 KB Output is correct
15 Correct 48 ms 10684 KB Output is correct
16 Correct 54 ms 10688 KB Output is correct
17 Correct 46 ms 9944 KB Output is correct
18 Correct 61 ms 11172 KB Output is correct
19 Correct 236 ms 60384 KB Output is correct
20 Correct 242 ms 59240 KB Output is correct
21 Correct 237 ms 58648 KB Output is correct
22 Correct 244 ms 59156 KB Output is correct
23 Correct 233 ms 58648 KB Output is correct
24 Correct 229 ms 59628 KB Output is correct