oj.uz

답안 #63898

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
63898 2018-08-03T06:32:35 Z 노영훈(#1868) Park (BOI16_park) C++11
0 / 100
 843 ms 37444 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double lf;
typedef pair<int, int> pii;
typedef pair<ll, pii> pli;
const int inf=2e9;

int w, h;
int n, m;


int U[2010];
int find(int x){ return x==U[x] ? x : U[x]=find(U[x]); }
void unite(int x, int y){ U[find(y)]=find(x); }

struct tree{
    int x, y, r;
    void scan(){ cin>>x>>y>>r; }
} T[2010];

inline bool go(int a, int b){ return find(n+a)!=find(n+b); }

//   3
// 4   2
//   1

inline int f(int x){ return (x+3)%4+1; }

bool valid(int to, int fr){
    if(to==fr) return true;
    if(!go(to, f(to-1)) || !go(fr, f(fr-1))) return false;
    if(f(fr+3)==to) swap(to, fr);
    if(f(fr+2)==to) return go(fr, f(fr+2)) && go(f(fr+1), f(fr+3));
    if(f(fr+1)==to) return go(fr, f(fr+2));
    assert(false);
}

struct man{
    ll r; int e, idx;
    vector<int> ans;
    void scan(){
        cin>>r>>e;
    }
    void save(){
        for(int k=1; k<=4; k++)
            if(valid(k,e)) ans.push_back(k);
    }
    void show(){
        for(int x:ans) cout<<x;
        cout<<'\n';
    }
} V[100010];

inline ll sq(ll x){ return x*x; }

ll dist(tree &a, tree &b){
    return sq(a.x-b.x)+sq(a.y-b.y);
}

//   3
// 4   2
//   1

// 올림
ll my_sqrt(ll x){
    ll s=0, e=min(ll(inf), x);
    while(s<e){
        ll m=(s+e)>>1;
        if(m*m>=x) e=m;
        else s=m+1;
    }
    return s;
}

ll gap(int a, int b){
    if(b<=n)
        return my_sqrt(dist(T[a], T[b]))-T[a].r-T[b].r;

    if(b-n==1) return T[a].y;
    if(b-n==2) return w-T[a].x;
    if(b-n==3) return h-T[a].y;
    if(b-n==4) return T[a].x;
    assert(false);
}

// bool stuck(man &v, pii &p){
//     int a,b; tie(a,b)=p;
//     if(b>n) return gap(a,b) < v.r*2;
//     return dist(T[a], T[b]) < sq(T[a].r+T[b].r+v.r*2);
// }


int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m>>w>>h;
    for(int i=1; i<=n; i++) T[i].scan();
    iota(U, U+n+4+1, 0);

    for(int i=1; i<=m; i++) V[i].scan(), V[i].idx=i;
    sort(V+1, V+m+1, [](man &a, man &b){ return a.r<b.r; });

    vector<pli> P;
    for(int i=1; i<=n; i++) for(int j=i+1; j<=n; j++) P.push_back({gap(i,j), {i,j}});
    for(int i=1; i<=n; i++) for(int k=1; k<=4; k++) P.push_back({gap(i,n+k), {i,n+k}});

    sort(P.begin(), P.end());

    // for(auto p:P) cout<<p.first<<' ';
    // cout<<'\n';

    for(int i=1, j=-1; i<=m; i++){
        while(j+1<(int)P.size() && V[i].r*2>P[j+1].first){
            int a,b; tie(a,b)=P[++j].second;
            unite(a,b);
            // cout<<"UNITE: "<<a<<' '<<b<<'\n';
        }
        V[i].save();
        // for(int i=1; i<=4; i++, cout<<'\n') for(int j=1; j<=4; j++) cout<<go(i,j)<<' ';
        // cout<<'\n';
    }

    sort(V+1, V+m+1, [](man &a, man &b){ return a.idx<b.idx; });
    for(int i=1; i<=m; i++) V[i].show();

    return 0;
}

Subtask #1
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 843 ms 37396 KB Output is correct
2 Incorrect 841 ms 37444 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

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

Subtask #3
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 843 ms 37396 KB Output is correct
2 Incorrect 841 ms 37444 KB Output isn't correct
3 Halted 0 ms 0 KB -