oj.uz

Submission #1024258

# Submission time Handle Problem Language Result Execution time Memory
1024258 2024-07-15T20:37:45 Z dpsaveslives Park (BOI16_park) C++17
100 / 100
 218 ms 35260 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct DSU{
    int N;
    vector<int> d;
    void init(int n){
        N = n;
        d = vector<int>(N,-1);
    }
    int finden(int x){
        if(d[x] < 0) return x;
        return (d[x] = finden(d[x]));
    }
    bool unite(int a, int b){
        a = finden(a), b = finden(b);
        if(a == b) return false;
        if(d[a] < d[b]) swap(a,b);
        d[b] += d[a]; d[a] = b;
        return true;
    }
};
struct edge{
    int u,v; ll w;
    bool operator<(const edge &b){
        return w < b.w;
    }
};
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int N,M; cin >> N >> M;
    int W,H; cin >> W >> H;
    vector<edge> edges;
    vector<ll> x(N+5),y(N+5),r(N+5);
    for(int i = 5;i<=N+4;++i){
        cin >> x[i] >> y[i] >> r[i]; edge e;
        e.u = 1; e.v = i; e.w = H-y[i]-r[i]; edges.push_back(e);
        e.u = 2; e.v = i; e.w = W-x[i]-r[i]; edges.push_back(e);
        e.u = 3; e.v = i; e.w = y[i]-r[i]; edges.push_back(e);
        e.u = 4; e.v = i; e.w = x[i]-r[i]; edges.push_back(e);
        for(int j = 5;j<i;++j){
            e.u = i; e.v = j; e.w = (ll)sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))-r[i]-r[j];
            edges.push_back(e);
        }
    }
    sort(edges.begin(),edges.end());
    DSU D; D.init(N+5);
    vector<vector<int>> res(5,vector<int>(5,-1));
    for(int i = 0;i<edges.size();++i){
        int u = edges[i].u, v = edges[i].v;
        ll w = edges[i].w;
        D.unite(u,v);
        for(int j = 1;j<=4;++j){
            for(int k = j+1;k<=4;++k){
                if(res[j][k] == -1 && D.finden(j) == D.finden(k)){
                    res[j][k] = res[k][j] = w;
                }
            }
        }
    }
    for(int i = 0;i<M;++i){
        ll rq; int en; cin >> rq >> en;
        rq *= 2;
        vector<bool> ok(5,true);
        if(en == 1){
            if(res[1][2] < rq){
                ok[3] = false;
            }
            if(res[1][3] < rq){
                ok[2] = ok[3] = false;
            }
            if(res[1][4] < rq){
                ok[4] = false;
            }
            if(res[2][3] < rq){
                ok[2] = false;
            }
            if(res[2][4] < rq){
                ok[3] = ok[4] = false;
            }
            if(res[3][4] < rq){
                ok[2] = ok[3] = ok[4] = false;
            }
        }
        else if(en == 2){
            if(res[3][4] < rq){
                ok[1] = false;
            }
            if(res[1][2] < rq){
                ok[3] = false;
            }
            if(res[1][4] < rq){
                ok[4] = false;
            }
            if(res[1][3] < rq){
                ok[1] = ok[4] = false;
            }
            if(res[2][3] < rq){
                ok[1] = ok[3] = ok[4] = false;
            }
            if(res[2][4] < rq){
                ok[3] = ok[4] = false;
            }

        }
        else if(en == 3){
            if(res[3][4] < rq){
                ok[1] = false;
            }
            if(res[2][3] < rq){
                ok[2] = false;
            }
            if(res[1][2] < rq){
                ok[1] = ok[2] = ok[4] = false;
            }
            if(res[1][4] < rq){
                ok[4] = false;
            }
            if(res[1][3] < rq){
                ok[1] = ok[4] = false;
            }
            if(res[2][4] < rq){
                ok[1] = ok[2] = false;
            }

        }
        else{
             if(res[3][4] < rq){
                ok[1] = false;
            }
            if(res[2][3] < rq){
                ok[2] = false;
            }
            if(res[1][2] < rq){
                ok[3] = false;
            }
            if(res[2][4] < rq){
                ok[1] = ok[2] = false;
            }
            if(res[1][3] < rq){
                ok[2] = ok[3] = false;
            }
            if(res[1][4] < rq){
                ok[2] = ok[3] = ok[1] = false;
            }

        }
        for(int j = 1;j<=4;++j){
            if(ok[j]) cout << j;
        }
        cout << "\n";
    }
    return 0;
}

Compilation message

park.cpp: In function 'int main()':
park.cpp:50:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int i = 0;i<edges.size();++i){
      |                   ~^~~~~~~~~~~~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 34240 KB Output is correct
2 Correct 192 ms 35008 KB Output is correct
3 Correct 194 ms 35260 KB Output is correct
4 Correct 192 ms 33728 KB Output is correct
5 Correct 184 ms 34492 KB Output is correct
6 Correct 191 ms 33980 KB Output is correct
7 Correct 189 ms 33984 KB Output is correct
8 Correct 183 ms 33700 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1244 KB Output is correct
2 Correct 23 ms 1244 KB Output is correct
3 Correct 22 ms 1244 KB Output is correct
4 Correct 22 ms 1208 KB Output is correct
5 Correct 22 ms 1160 KB Output is correct
6 Correct 30 ms 1080 KB Output is correct
7 Correct 20 ms 648 KB Output is correct
8 Correct 20 ms 600 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 34240 KB Output is correct
2 Correct 192 ms 35008 KB Output is correct
3 Correct 194 ms 35260 KB Output is correct
4 Correct 192 ms 33728 KB Output is correct
5 Correct 184 ms 34492 KB Output is correct
6 Correct 191 ms 33980 KB Output is correct
7 Correct 189 ms 33984 KB Output is correct
8 Correct 183 ms 33700 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 23 ms 1244 KB Output is correct
12 Correct 23 ms 1244 KB Output is correct
13 Correct 22 ms 1244 KB Output is correct
14 Correct 22 ms 1208 KB Output is correct
15 Correct 22 ms 1160 KB Output is correct
16 Correct 30 ms 1080 KB Output is correct
17 Correct 20 ms 648 KB Output is correct
18 Correct 20 ms 600 KB Output is correct
19 Correct 209 ms 35008 KB Output is correct
20 Correct 204 ms 33980 KB Output is correct
21 Correct 218 ms 33472 KB Output is correct
22 Correct 212 ms 33728 KB Output is correct
23 Correct 211 ms 34240 KB Output is correct
24 Correct 202 ms 33716 KB Output is correct