oj.uz

Submission #1097831

# Submission time Handle Problem Language Result Execution time Memory
1097831 2024-10-08T09:59:00 Z pemguimn Park (BOI16_park) C++14
100 / 100
 302 ms 137884 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 2e3 + 10, M = 1e5 + 5;
int n, m, w, h, x[N], y[N], r[N], R[M], e[M], par[N], sz[N];
struct ev{
    long long dist;
    int t, x, y;
};

string res[M];

int root(int x){
    if(x == par[x]) return x;
    return par[x] = (root(par[x]));
}

void unite(int x, int y){
    x = root(x), y = root(y);
    if(x != y){
        if(sz[x] < sz[y]) swap(x, y);
        sz[x] += sz[y];
        par[y] = x;
    }
}

bool bound(int x, int y){
    return (root(x) == root(y));
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> w >> h;
    for(int i = 1; i <= n + 4; i++) par[i] = i, sz[i] = 1;
    for(int i = 1; i <= n; i++){
        cin >> x[i] >> y[i] >> r[i];
    }
    vector<ev> events;
    for(int i = 1; i <= n; i++){
        events.push_back({1LL * y[i] - r[i], 1, i, n + 1});
        events.push_back({1LL * (w - x[i]) - r[i], 1, i, n + 2});
        events.push_back({1LL * (h - y[i]) - r[i], 1, i, n + 3});
        events.push_back({1LL * x[i] - r[i], 1, i, n + 4});
    }
    for(int i = 1; i <= n; i++){
        for(int j = i + 1; j <= n; j++){
            long long dx = x[i] - x[j];
            long long dy = y[i] - y[j];
            long long rounded = sqrt(1LL * dx * dx + dy * dy);
            events.push_back({rounded - r[i] - r[j], 1, i, j});
        }
    }
    for(int i = 1; i <= m; i++){
        cin >> R[i] >> e[i];
        events.push_back({2LL * R[i], 0, i, 0});
    }
    sort(events.begin(), events.end(), [](ev x, ev y){
        return x.dist < y.dist || (x.dist == y.dist && x.t < y.t);
    });

    for(ev cur : events){
        if(cur.t == 1){
            unite(cur.x, cur.y);
        } else{
            string ans = "";
            bool go1 = true;
            bool go2 = true;
            bool go3 = true;
            bool go4 = true;

            if(e[cur.x] == 1){
                // Vertical
                if(bound(n + 1, n + 3)) go2 = go3 = false;
                if(bound(n + 1, n + 4)) go2 = go4 = go3 = false;
                // Horizontal
                if(bound(n + 2, n + 4)) go4 = go3 = false;
                if(bound(n + 1, n + 2)) go2 = false;
                if(bound(n + 2, n + 3)) go3 = false;
                if(bound(n + 3, n + 4)) go4 = false;
            } else if(e[cur.x] == 2){
                // Vertical
                if(bound(n + 1, n + 3)) go1 = go4 = false;
                if(bound(n + 1, n + 2)) go1 = go3 = go4 = false;
                // Horizontal
                if(bound(n + 2, n + 4)) go4 = go3 = false;
                if(bound(n + 1, n + 4)) go1 = false;
                if(bound(n + 2, n + 3)) go3 = false;
                if(bound(n + 3, n + 4)) go4 = false;
            } else if(e[cur.x] == 3){
                if(bound(n + 1, n + 3)) go1 = go4 = false;
                if(bound(n + 2, n + 4)) go1 = go2 = false;
                if(bound(n + 2, n + 3)) go1 = go2 = go4 = false;
                if(bound(n + 1, n + 4)) go1 = false;
                if(bound(n + 1, n + 2)) go2 = false;
                if(bound(n + 3, n + 4)) go4 = false;
            } else{
                if(bound(n + 1, n + 3)) go2 = go3 = false;
                if(bound(n + 2, n + 4)) go1 = go2 = false;
                if(bound(n + 3, n + 4)) go1 = go3 = go2 = false;
                if(bound(n + 1, n + 4)) go1 = false;
                if(bound(n + 1, n + 2)) go2 = false;
                if(bound(n + 2, n + 3)) go3 = false;
            }

            if(go1) ans += "1";
            if(go2) ans += "2";
            if(go3) ans += "3";
            if(go4) ans += "4";
            res[cur.x] = ans;
        }
    }
    for(int i = 1; i <= m; i++) cout << res[i] << "\n";
    return 0;
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 71876 KB Output is correct
2 Correct 211 ms 71336 KB Output is correct
3 Correct 227 ms 71100 KB Output is correct
4 Correct 216 ms 70848 KB Output is correct
5 Correct 228 ms 71336 KB Output is correct
6 Correct 223 ms 70824 KB Output is correct
7 Correct 193 ms 70596 KB Output is correct
8 Correct 210 ms 71344 KB Output is correct
9 Correct 1 ms 4700 KB Output is correct
10 Correct 1 ms 4700 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 9428 KB Output is correct
2 Correct 29 ms 9940 KB Output is correct
3 Correct 31 ms 10452 KB Output is correct
4 Correct 32 ms 10196 KB Output is correct
5 Correct 33 ms 9936 KB Output is correct
6 Correct 29 ms 10708 KB Output is correct
7 Correct 29 ms 9424 KB Output is correct
8 Correct 29 ms 10960 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 71876 KB Output is correct
2 Correct 211 ms 71336 KB Output is correct
3 Correct 227 ms 71100 KB Output is correct
4 Correct 216 ms 70848 KB Output is correct
5 Correct 228 ms 71336 KB Output is correct
6 Correct 223 ms 70824 KB Output is correct
7 Correct 193 ms 70596 KB Output is correct
8 Correct 210 ms 71344 KB Output is correct
9 Correct 1 ms 4700 KB Output is correct
10 Correct 1 ms 4700 KB Output is correct
11 Correct 46 ms 9428 KB Output is correct
12 Correct 29 ms 9940 KB Output is correct
13 Correct 31 ms 10452 KB Output is correct
14 Correct 32 ms 10196 KB Output is correct
15 Correct 33 ms 9936 KB Output is correct
16 Correct 29 ms 10708 KB Output is correct
17 Correct 29 ms 9424 KB Output is correct
18 Correct 29 ms 10960 KB Output is correct
19 Correct 293 ms 137884 KB Output is correct
20 Correct 287 ms 136596 KB Output is correct
21 Correct 289 ms 136608 KB Output is correct
22 Correct 302 ms 136424 KB Output is correct
23 Correct 297 ms 136404 KB Output is correct
24 Correct 263 ms 136608 KB Output is correct