oj.uz

답안 #385790

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
385790 2021-04-05T00:32:39 Z erfanmir Park (BOI16_park) C++17
0 / 100
 531 ms 89976 KB 
// In the name of god

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;
using namespace __gnu_pbds; 

template < class T > using ordered_set = tree < T , null_type , less < T > , rb_tree_tag , tree_order_statistics_node_update >;
  
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;

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 = 0; 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 = 0; 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));
    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++;
        }
        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:3: warning: ignoring #pragma comment  [-Wunknown-pragmas]
    3 | #pragma comment(linker, "/stack:200000000")
      | 
park.cpp: In function 'int main()':
park.cpp:95:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   95 |     scanf("%lld %lld %lld %lld", &n, &m, &w, &h);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:97:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   97 |         scanf("%lld %lld %lld\n", x + i, y + i, r + i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:115:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  115 |         scanf("%lld %lld", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 522 ms 89616 KB Output is correct
2 Correct 518 ms 89616 KB Output is correct
3 Correct 529 ms 89616 KB Output is correct
4 Correct 517 ms 89648 KB Output is correct
5 Correct 523 ms 89616 KB Output is correct
6 Correct 529 ms 89664 KB Output is correct
7 Correct 531 ms 89616 KB Output is correct
8 Incorrect 506 ms 89976 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 113 ms 31576 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 522 ms 89616 KB Output is correct
2 Correct 518 ms 89616 KB Output is correct
3 Correct 529 ms 89616 KB Output is correct
4 Correct 517 ms 89648 KB Output is correct
5 Correct 523 ms 89616 KB Output is correct
6 Correct 529 ms 89664 KB Output is correct
7 Correct 531 ms 89616 KB Output is correct
8 Incorrect 506 ms 89976 KB Output isn't correct
9 Halted 0 ms 0 KB -