oj.uz

Submission #385791

# Submission time Handle Problem Language Result Execution time Memory
385791 2021-04-05T00:44:13 Z erfanmir Park (BOI16_park) C++11
100 / 100
 696 ms 94924 KB 
// 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

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.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 522 ms 89616 KB Output is correct
2 Correct 561 ms 89636 KB Output is correct
3 Correct 528 ms 89616 KB Output is correct
4 Correct 524 ms 89616 KB Output is correct
5 Correct 529 ms 89596 KB Output is correct
6 Correct 528 ms 89616 KB Output is correct
7 Correct 570 ms 89616 KB Output is correct
8 Correct 504 ms 89776 KB Output is correct
9 Correct 15 ms 23788 KB Output is correct
10 Correct 16 ms 23788 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 31576 KB Output is correct
2 Correct 123 ms 32088 KB Output is correct
3 Correct 120 ms 31832 KB Output is correct
4 Correct 126 ms 32216 KB Output is correct
5 Correct 127 ms 32384 KB Output is correct
6 Correct 127 ms 32216 KB Output is correct
7 Correct 124 ms 31196 KB Output is correct
8 Correct 108 ms 31196 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 522 ms 89616 KB Output is correct
2 Correct 561 ms 89636 KB Output is correct
3 Correct 528 ms 89616 KB Output is correct
4 Correct 524 ms 89616 KB Output is correct
5 Correct 529 ms 89596 KB Output is correct
6 Correct 528 ms 89616 KB Output is correct
7 Correct 570 ms 89616 KB Output is correct
8 Correct 504 ms 89776 KB Output is correct
9 Correct 15 ms 23788 KB Output is correct
10 Correct 16 ms 23788 KB Output is correct
11 Correct 133 ms 31576 KB Output is correct
12 Correct 123 ms 32088 KB Output is correct
13 Correct 120 ms 31832 KB Output is correct
14 Correct 126 ms 32216 KB Output is correct
15 Correct 127 ms 32384 KB Output is correct
16 Correct 127 ms 32216 KB Output is correct
17 Correct 124 ms 31196 KB Output is correct
18 Correct 108 ms 31196 KB Output is correct
19 Correct 633 ms 94412 KB Output is correct
20 Correct 622 ms 94284 KB Output is correct
21 Correct 639 ms 94924 KB Output is correct
22 Correct 624 ms 94132 KB Output is correct
23 Correct 626 ms 94412 KB Output is correct
24 Correct 696 ms 94540 KB Output is correct