oj.uz

Submission #643190

# Submission time Handle Problem Language Result Execution time Memory
643190 2022-09-21T12:38:44 Z fatemetmhr Park (BOI16_park) C++17
0 / 100
 259 ms 36928 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){
    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(double(a * a + b * b));
            ll need = c - r[i] - r[j];
            need /= 2;
            ll c2 = need * 2 + r[i] + r[j]; c2 = c2 * c2;
            if(c2 != a * a + b * b)
                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:79: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]
   79 |         while(ind < ed.size() && ed[ind].fi <= red){
      |               ~~~~^~~~~~~~~~~

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 36920 KB Output is correct
2 Correct 233 ms 36908 KB Output is correct
3 Correct 242 ms 36856 KB Output is correct
4 Correct 233 ms 36872 KB Output is correct
5 Correct 259 ms 36920 KB Output is correct
6 Correct 230 ms 36856 KB Output is correct
7 Correct 232 ms 36928 KB Output is correct
8 Incorrect 211 ms 36860 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 7292 KB Output is correct
2 Correct 46 ms 7328 KB Output is correct
3 Correct 48 ms 7268 KB Output is correct
4 Correct 50 ms 7196 KB Output is correct
5 Correct 45 ms 7252 KB Output is correct
6 Incorrect 48 ms 7300 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 36920 KB Output is correct
2 Correct 233 ms 36908 KB Output is correct
3 Correct 242 ms 36856 KB Output is correct
4 Correct 233 ms 36872 KB Output is correct
5 Correct 259 ms 36920 KB Output is correct
6 Correct 230 ms 36856 KB Output is correct
7 Correct 232 ms 36928 KB Output is correct
8 Incorrect 211 ms 36860 KB Output isn't correct
9 Halted 0 ms 0 KB -