oj.uz

Submission #643208

# Submission time Handle Problem Language Result Execution time Memory
643208 2022-09-21T13:15:49 Z fatemetmhr Park (BOI16_park) C++17
100 / 100
 279 ms 40416 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb       push_back
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn5 = 1e5 + 10;
const int inf   = 1e9;

int par[maxn5];
vector <pair<ll, pair<int, int>>> ed, req;
vector <int> gr1[6][6], gr2[6][6];
ll x[maxn5], y[maxn5], r[maxn5];
string out[maxn5];

int get_par(int a){return par[a] == -1 ? a : par[a] = get_par(par[a]);}

inline void merge(int a, int b){
    a = get_par(a); b = get_par(b);
    //cout << "req a merge of " << a << ' ' << b << endl;
    if(a == b)
        return;
    par[a] = b;
    return;
}

inline ll sg(ll a){
    a++;
    return a / 2 + a % 2;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int n, m; cin >> n >> m;
    ll h, w; cin >> w >> h;
    memset(par, -1, sizeof par);
    for(int i = 0; i < n; i++){
        cin >> x[i] >> y[i] >> r[i];
        for(int j = 0; j < i; j++){
            ll a = x[i] - x[j], b = y[i] - y[j];
            ll c = sqrt(a * a + b * b);
            ll need = c - r[i] - r[j];
            need /= 2;
            need++;
            ed.pb({need, {i, j}});
        }
        ed.pb({sg(x[i] - r[i]), {i, n}});
        ed.pb({sg(h - y[i] - r[i]), {i, n + 1}});
        ed.pb({sg(w - x[i] - r[i]), {i, n + 2}});
        ed.pb({sg(y[i] - r[i]), {i, n + 3}});
    }


    gr1[1][2] = {n + 3}; gr2[1][2] = {n + 2, n + 1, n};
    gr1[1][3] = {n + 3, n + 2}; gr2[1][3] = {n + 1, n};
    gr1[1][4] = {n}; gr2[1][4] = {n + 2, n + 1, n + 3};
    gr1[2][3] = {n + 2}; gr2[2][3] = {n + 1, n, n + 3};
    gr1[2][4] = {n, n + 3}; gr2[2][4] = {n + 2, n + 1};
    gr1[3][4] = {n, n + 3, n + 2}; gr2[3][4] = {n + 1};

    sort(all(ed));
    for(int i = 0; i < m; i++){
        int r, e; cin >> r >> e;
        req.pb({r, {e, i}});
    }
    sort(all(req));
    int ind = 0;
    for(auto p : req){
        int red = p.fi, ent = p.se.fi, id = p.se.se;
        //cout << "having " << id << ' ' << red << ' ' << ent << endl;
        while(ind < ed.size() && ed[ind].fi <= red){
            merge(ed[ind].se.fi, ed[ind].se.se);
            ind++;
        }
        for(int i = 1; i <= 4; i++){
            if(ent == i){
                out[id].pb(char(i + '0'));
                continue;
            }
            int v = min(i, ent), u = max(i, ent);
            bool re = true;
            for(auto t1 : gr1[v][u]) for(auto t2 : gr2[v][u]) if(get_par(t1) == get_par(t2))
                re = false;
            if(re)
                out[id].pb(char(i + '0'));
        }
    }
    for(int i = 0; i < m; i++)
        cout << out[i] << '\n';
}

Compilation message

park.cpp: In function 'int main()':
park.cpp:78:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         while(ind < ed.size() && ed[ind].fi <= red){
      |               ~~~~^~~~~~~~~~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 36784 KB Output is correct
2 Correct 229 ms 36792 KB Output is correct
3 Correct 226 ms 36844 KB Output is correct
4 Correct 234 ms 36836 KB Output is correct
5 Correct 228 ms 36864 KB Output is correct
6 Correct 230 ms 36800 KB Output is correct
7 Correct 213 ms 36852 KB Output is correct
8 Correct 210 ms 36824 KB Output is correct
9 Correct 2 ms 3796 KB Output is correct
10 Correct 2 ms 3796 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 6360 KB Output is correct
2 Correct 44 ms 6280 KB Output is correct
3 Correct 45 ms 6356 KB Output is correct
4 Correct 50 ms 6356 KB Output is correct
5 Correct 45 ms 6384 KB Output is correct
6 Correct 46 ms 6356 KB Output is correct
7 Correct 43 ms 7028 KB Output is correct
8 Correct 42 ms 6992 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 36784 KB Output is correct
2 Correct 229 ms 36792 KB Output is correct
3 Correct 226 ms 36844 KB Output is correct
4 Correct 234 ms 36836 KB Output is correct
5 Correct 228 ms 36864 KB Output is correct
6 Correct 230 ms 36800 KB Output is correct
7 Correct 213 ms 36852 KB Output is correct
8 Correct 210 ms 36824 KB Output is correct
9 Correct 2 ms 3796 KB Output is correct
10 Correct 2 ms 3796 KB Output is correct
11 Correct 49 ms 6360 KB Output is correct
12 Correct 44 ms 6280 KB Output is correct
13 Correct 45 ms 6356 KB Output is correct
14 Correct 50 ms 6356 KB Output is correct
15 Correct 45 ms 6384 KB Output is correct
16 Correct 46 ms 6356 KB Output is correct
17 Correct 43 ms 7028 KB Output is correct
18 Correct 42 ms 6992 KB Output is correct
19 Correct 274 ms 40328 KB Output is correct
20 Correct 279 ms 40304 KB Output is correct
21 Correct 271 ms 40380 KB Output is correct
22 Correct 277 ms 40224 KB Output is correct
23 Correct 268 ms 40356 KB Output is correct
24 Correct 262 ms 40416 KB Output is correct