oj.uz

Submission #1097797

# Submission time Handle Problem Language Result Execution time Memory
1097797 2024-10-08T09:38:47 Z Icelast Park (BOI16_park) C++17
0 / 100
 389 ms 80792 KB 
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
const long double eps = 1e-9;
struct DSU{
    int n;
    vector<int> pa, sz;
    DSU(int n) : n(n){
        pa.resize(n+1);
        sz.resize(n+1, 1);
        for(int i = 0; i <= n; i++){
            pa[i] = i;
        }
    };
    int find(int x){
        while(x != pa[x]){
            x = pa[x] = pa[pa[x]];
        }
        return x;
    }
    bool same(int x, int y){
        return find(x) == find(y);
    }
    bool merge(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return false;
        if(sz[x] < sz[y]) swap(x, y);
        pa[y] = x;
        sz[x] += sz[y];
        return true;
    }
    int size(int x){
        return sz[find(x)];
    }
};
struct plant{
    ll x, y, r;
};
struct man{
    ll t, r, id;
};
struct edge{
    int u, v;
    long double w;
};
void solve(){
    int n, m;
    cin >> n >> m;
    ll w, h;
    cin >> w >> h;
    vector<plant> a(n+1);
    for(int i = 1; i <= n; i++){
        cin >> a[i].x >> a[i].y >> a[i].r;
    }
    vector<man> b(m+1);
    for(int i = 1; i <= m; i++){
        cin >> b[i].r >> b[i].t;
        b[i].id = i;
    }
    auto d = [&](int i, int j) -> long double{
        return sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x) + (a[i].y-a[j].y)*(a[i].y-a[j].y));
    };
    vector<edge> pr;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j < i; j++){
            pr.push_back({i, j, d(i, j)-a[i].r-a[j].r});
        }
        pr.push_back({i, n+1, a[i].y-a[i].r});
        pr.push_back({i, n+2, w-a[i].x-a[i].r});
        pr.push_back({i, n+3, h-a[i].y-a[i].r});
        pr.push_back({i, n+4, a[i].x-a[i].r});
    }
    sort(b.begin()+1, b.end(), [&](man a, man b){return a.r < b.r;});
    sort(pr.begin(), pr.end(), [&](edge a, edge b){return a.w < b.w;});
    int j = 0;
    auto cmp = [&](long double a, long double b) -> bool{
        return b-a > eps;
    };
    int N = pr.size()+10;
    DSU dsu(N);
    vector<int> s;
    vector<vector<int>> ans(m+1);
    for(int i = 1; i <= m; i++){
        while(j < pr.size() && cmp(pr[j].w, b[i].r*2)){
            dsu.merge(pr[j].u, pr[j].v);
            j++;
        }
        int id = b[i].id;
        s.clear();
        if(b[i].t == 1){
            s.push_back(1);
            if(dsu.same(n+1, n+2) || dsu.same(n+1, n+3) || dsu.same(n+1, n+4)){

            }else{
                s.push_back(2);
            }
            if(dsu.same(n+1, n+3) || dsu.same(n+2, n+3) || dsu.same(n+2, n+4) || dsu.same(n+1, n+4)){

            }else{
                s.push_back(3);
            }
            if(dsu.same(n+1, n+4) || dsu.same(n+2, n+4) || dsu.same(n+3, n+4)){

            }else{
                s.push_back(4);
            }
        }
        if(b[i].t == 2){
            s.push_back(2);
            if(dsu.same(n+1, n+2) || dsu.same(n+1, n+3) || dsu.same(n+1, n+4)){

            }else{
                s.push_back(1);
            }
            if(dsu.same(n+1, n+2) || dsu.same(n+2, n+3) || dsu.same(n+2, n+4)){

            }else{
                s.push_back(3);
            }
            if(dsu.same(n+1, n+2) || dsu.same(n+2, n+4) || dsu.same(n+3, n+4) || dsu.same(n+1, n+3)){

            }else{
                s.push_back(4);
            }
        }
        if(b[i].t == 3){
            s.push_back(3);
            if(dsu.same(n+1, n+3) || dsu.same(n+1, n+4) || dsu.same(n+2, n+3), dsu.same(n+2, n+4)){

            }else{
                s.push_back(1);
            }
            if(dsu.same(n+1, n+2) || dsu.same(n+2, n+3) || dsu.same(n+2, n+4)){

            }else{
                s.push_back(2);
            }
            if(dsu.same(n+1, n+3) || dsu.same(n+2, n+3) || dsu.same(n+3, n+4)){

            }else{
                s.push_back(4);
            }
        }
        if(b[i].t == 4){
            s.push_back(4);
            if(dsu.same(n+1, n+4) || dsu.same(n+2, n+4) || dsu.same(n+3, n+4)){

            }else{
                s.push_back(1);
            }
            if(dsu.same(n+1, n+2) || dsu.same(n+2, n+4) || dsu.same(n+3, n+4) || dsu.same(n+1, n+3)){

            }else{
                s.push_back(2);
            }
            if(dsu.same(n+1, n+3) || dsu.same(n+2, n+3) || dsu.same(n+2, n+4)){

            }else{
                s.push_back(3);
            }
        }
        sort(s.begin(), s.end());
        ans[id] = s;
    }
    for(int i = 1; i <= m; i++){
        for(int j : ans[i]){
            cout << j;
        }
        cout << "\n";
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

Compilation message

park.cpp: In function 'void solve()':
park.cpp:71:37: warning: narrowing conversion of '(a.std::vector<plant>::operator[](((std::vector<plant>::size_type)i)).plant::y - a.std::vector<plant>::operator[](((std::vector<plant>::size_type)i)).plant::r)' from 'long long int' to 'long double' [-Wnarrowing]
   71 |         pr.push_back({i, n+1, a[i].y-a[i].r});
park.cpp:72:39: warning: narrowing conversion of '((w - a.std::vector<plant>::operator[](((std::vector<plant>::size_type)i)).plant::x) - a.std::vector<plant>::operator[](((std::vector<plant>::size_type)i)).plant::r)' from 'long long int' to 'long double' [-Wnarrowing]
   72 |         pr.push_back({i, n+2, w-a[i].x-a[i].r});
      |                               ~~~~~~~~^~~~~~~
park.cpp:73:39: warning: narrowing conversion of '((h - a.std::vector<plant>::operator[](((std::vector<plant>::size_type)i)).plant::y) - a.std::vector<plant>::operator[](((std::vector<plant>::size_type)i)).plant::r)' from 'long long int' to 'long double' [-Wnarrowing]
   73 |         pr.push_back({i, n+3, h-a[i].y-a[i].r});
      |                               ~~~~~~~~^~~~~~~
park.cpp:74:37: warning: narrowing conversion of '(a.std::vector<plant>::operator[](((std::vector<plant>::size_type)i)).plant::x - a.std::vector<plant>::operator[](((std::vector<plant>::size_type)i)).plant::r)' from 'long long int' to 'long double' [-Wnarrowing]
   74 |         pr.push_back({i, n+4, a[i].x-a[i].r});
park.cpp:87:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         while(j < pr.size() && cmp(pr[j].w, b[i].r*2)){
      |               ~~^~~~~~~~~~~

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 79252 KB Output is correct
2 Correct 371 ms 80792 KB Output is correct
3 Correct 368 ms 79516 KB Output is correct
4 Correct 365 ms 79328 KB Output is correct
5 Correct 389 ms 80788 KB Output is correct
6 Incorrect 380 ms 80668 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 9424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 79252 KB Output is correct
2 Correct 371 ms 80792 KB Output is correct
3 Correct 368 ms 79516 KB Output is correct
4 Correct 365 ms 79328 KB Output is correct
5 Correct 389 ms 80788 KB Output is correct
6 Incorrect 380 ms 80668 KB Output isn't correct
7 Halted 0 ms 0 KB -