Submission #643203

#	Time	Username	Problem	Language	Result	Execution time	Memory
643203		fatemetmhr	Park (BOI16_park)	C++17	0 / 100	29 ms	3908 KiB

park

#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;
    ll a = inf, b = inf;
    //cout << sqrt(a * a + b * b) << endl;
    memset(par, -1, sizeof par);
    for(int i = 0; i < n; i++){
        cin >> x[i] >> y[i] >> r[i];
        continue;
        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;
            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}});
    }

    ll red; int ent;
    cin >> red >> ent;

    for(int i = 0; i < n; i++)
        r[i] += red;

    for(int i = 0; i < n; 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);
            if(c <= r[i] + r[j])
                merge(i, j);
            continue;
            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}});
        }
        if(x[i] - r[i] - red <= 0)
            merge(i, n);
        if(h - y[i] - r[i] - red <= 0)
            merge(i, n + 1);
        if(w - x[i] - r[i] - red <= 0)
            merge(i, n + 2);
        if(y[i] - r[i] - red <= 0)
            merge(i, n + 3);
        continue;
        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};

    for(int i = 1; i <= 4; i++){
        if(ent == i){
            cout << i;
            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)
            cout << i;
    }
    cout << endl;
    return 0;

    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';
}

/*
5 1
16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 1
2 2
2 1
*/

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:132: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]
  132 |         while(ind < ed.size() && ed[ind].fi <= red){
      |               ~~~~^~~~~~~~~~~
park.cpp:42:8: warning: unused variable 'a' [-Wunused-variable]
   42 |     ll a = inf, b = inf;
      |        ^
park.cpp:42:17: warning: unused variable 'b' [-Wunused-variable]
   42 |     ll a = inf, b = inf;
      |                 ^

• Subtask 1: 0 / 27
• Subtask 2: 0 / 31
• Subtask 3: 0 / 42