oj.uz

답안 #1097799

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1097799 2024-10-08T09:39:57 Z pemguimn Park (BOI16_park) C++14
27 / 100
 430 ms 104856 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 double 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;
    swap(w, h);
    for(int i = 1; i <= n; i++){
        cin >> x[i] >> y[i] >> r[i];
        swap(x[i], y[i]);
    }
    vector<ev> events;
    for(int i = 1; i <= n; i++){
        events.push_back({1LL * x[i] - r[i], 1, i, n + 1});
        events.push_back({1LL * (h - y[i]) - r[i], 1, i, n + 2});
        events.push_back({1LL * (w - x[i]) - r[i], 1, i, n + 3});
        events.push_back({1LL * y[i] - r[i], 1, i, n + 4});
    }
    for(int i = 1; i <= n; i++){
        for(int j = i + 1; j <= n; j++){
            long double dx = x[i] - x[j];
            long double dy = y[i] - y[j];
            events.push_back({sqrt(1LL * dx * dx + dy * dy) - 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){
                if(bound(n + 1, n + 3)) go2 = go3 = false;
                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;
                // 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 + 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)) go1 = go4 = false;
                if(bound(n + 2, n + 4)) go1 = 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;
}

Compilation message

park.cpp: In function 'int main()':
park.cpp:45:38: warning: narrowing conversion of '((1 * x[i]) - r[i])' from 'long long int' to 'long double' [-Wnarrowing]
   45 |         events.push_back({1LL * x[i] - r[i], 1, i, n + 1});
      |                           ~~~~~~~~~~~^~~~~~
park.cpp:46:44: warning: narrowing conversion of '((1 * (h - y[i])) - r[i])' from 'long long int' to 'long double' [-Wnarrowing]
   46 |         events.push_back({1LL * (h - y[i]) - r[i], 1, i, n + 2});
      |                           ~~~~~~~~~~~~~~~~~^~~~~~
park.cpp:47:44: warning: narrowing conversion of '((1 * (w - x[i])) - r[i])' from 'long long int' to 'long double' [-Wnarrowing]
   47 |         events.push_back({1LL * (w - x[i]) - r[i], 1, i, n + 3});
      |                           ~~~~~~~~~~~~~~~~~^~~~~~
park.cpp:48:38: warning: narrowing conversion of '((1 * y[i]) - r[i])' from 'long long int' to 'long double' [-Wnarrowing]
   48 |         events.push_back({1LL * y[i] - r[i], 1, i, n + 4});
      |                           ~~~~~~~~~~~^~~~~~
park.cpp:59:31: warning: narrowing conversion of '(2 * R[i])' from 'long long int' to 'long double' [-Wnarrowing]
   59 |         events.push_back({2LL * R[i], 0, i, 0});
      |                           ~~~~^~~~~~

Subtask #1
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 425 ms 104616 KB Output is correct
2 Correct 430 ms 104852 KB Output is correct
3 Correct 407 ms 104348 KB Output is correct
4 Correct 408 ms 103344 KB Output is correct
5 Correct 402 ms 103356 KB Output is correct
6 Correct 404 ms 103212 KB Output is correct
7 Correct 398 ms 103332 KB Output is correct
8 Correct 409 ms 104856 KB Output is correct
9 Correct 1 ms 4696 KB Output is correct
10 Correct 1 ms 4700 KB Output is correct

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 42 ms 11208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 425 ms 104616 KB Output is correct
2 Correct 430 ms 104852 KB Output is correct
3 Correct 407 ms 104348 KB Output is correct
4 Correct 408 ms 103344 KB Output is correct
5 Correct 402 ms 103356 KB Output is correct
6 Correct 404 ms 103212 KB Output is correct
7 Correct 398 ms 103332 KB Output is correct
8 Correct 409 ms 104856 KB Output is correct
9 Correct 1 ms 4696 KB Output is correct
10 Correct 1 ms 4700 KB Output is correct
11 Incorrect 42 ms 11208 KB Output isn't correct
12 Halted 0 ms 0 KB -