Submission #385791

#	Time	Username	Problem	Language	Result	Execution time	Memory
385791		erfanmir	Park (BOI16_park)	C++11	100 / 100	696 ms	94924 KiB

park

// In the name of god

#include <bits/stdc++.h>
using namespace std;
  
typedef long long                   ll;
typedef long double                 ld;
typedef pair<ll,ll>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define lc(x)                       (x) << 1
#define rc(x)                       (x) << 1 | 1
#define F                           first
#define S                           second
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define mp                          make_pair
ll poww(ll a, ll b, ll md) {
    ll ans = 1;
    for(; b; b >>= 1, a = a * a % md){
        if(b & 1){
            ans = ans * a % md;
        }
    }
    return ans % md;
}

const ll MAXN = 1e6 + 10;
const ll MAXLG = 18;
const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll INF = 8e18;
const ld ep = 1e-12;
ll n, m, w, h;
ll par[MAXN], sz[MAXN];
ll x[MAXN], y[MAXN], r[MAXN];
ll ans[5][5];
vector<ll> res[MAXN];
vector<pair<ld, pll> > edge;
vector<pair<pll, ll> > q;

bool cmp(pair<pll, ll> a, pair<pll, ll> b){
    return a.F < b.F;
}

ll getroot(ll v){
    if(par[v] == v){
        return v;
    }
    return par[v] = getroot(par[v]);
}

void merg(ll v, ll u){
    v = getroot(v);
    u = getroot(u);
    if(v == u){
        return;
    }
    if(sz[v] < sz[u]){
        swap(v, u);
    }
    par[u] = v;
    sz[v] += sz[u];
}

void preprocess(){
    ll st[5];
    for(ll i = 1; i <= 4; i++){
        st[i] = getroot(n + i);
    }
    ans[1][2] = (st[1] != st[2]) && (st[2] != st[3]) && (st[2] != st[4]);
    ans[2][3] = (st[2] != st[3]) && (st[3] != st[4]) && (st[3] != st[1]);
    ans[3][4] = (st[3] != st[4]) && (st[4] != st[1]) && (st[4] != st[2]);
    ans[1][3] = (st[1] != st[2]) && (st[3] != st[4]) && (st[1] != st[3]) && (st[2] != st[4]);
    ans[2][4] = (st[1] != st[4]) && (st[3] != st[2]) && (st[1] != st[3]) && (st[2] != st[4]);
    ans[1][4] = (st[4] != st[1]) && (st[1] != st[2]) && (st[1] != st[3]);
    for(ll i = 1; i <= 4; i++){
        for(ll j = 1; j <= 4; j++){
            if(i == j){
                ans[i][j] = 1;
            }
            if(i > j){
                ans[i][j] = ans[j][i];
            }
        }
    }
}

int main()
{
    scanf("%lld %lld %lld %lld", &n, &m, &w, &h);
    for(ll i = 1; i <= n; i++){
        scanf("%lld %lld %lld\n", x + i, y + i, r + i);
        ld tmp = x[i] - r[i];
        edge.push_back(mp(tmp, mp(i, n + 1)));
        tmp = w - x[i] - r[i];
        edge.push_back(mp(tmp, mp(i, n + 3)));
        tmp = y[i] - r[i];
        edge.push_back(mp(tmp, mp(i, n + 2)));
        tmp = h - y[i] - r[i];
        edge.push_back(mp(tmp, mp(i, n + 4)));
        for(ll j = 1; j < i; j++){
            ll dx = abs(x[i] - x[j]);
            ll dy = abs(y[i] - y[j]);
            tmp = sqrt(dx * dx + dy * dy) - 1.0 * r[i] - 1.0 * r[j];
            edge.push_back(mp(tmp, mp(j, i)));
        }
    }
    for(ll i = 0; i < m; i++){
        ll a, b;
        scanf("%lld %lld", &a, &b);
        a *= 2;
        q.push_back(mp(mp(a, b), i));
    }
    sort(all(edge));
    sort(all(q), cmp);
    for(ll i = 0; i < n + 4; i++){
        par[i] = i;
        sz[i] = 1;
    }
    ll cnt = 0;
    for(ll i = 0; i < m; i++){
        while(cnt < (ll)edge.size() && ep < q[i].F.F - edge[cnt].F){
            merg(edge[cnt].S.F, edge[cnt].S.S);
            preprocess();
            cnt++;
        }
        preprocess();
        for(ll j = 1; j <= 4; j++){
            if(ans[q[i].F.S][j]){
                res[q[i].S].push_back(j);
            }
        }
    }
    for(ll i = 0; i < m; i++){
        for(auto u : res[i]){
            printf("%lld", u);
        }
        printf("\n");
    }
}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   91 |     scanf("%lld %lld %lld %lld", &n, &m, &w, &h);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   93 |         scanf("%lld %lld %lld\n", x + i, y + i, r + i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:111:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  111 |         scanf("%lld %lld", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

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