oj.uz

Submission #63890

# Submission time Handle Problem Language Result Execution time Memory
63890 2018-08-03T06:17:58 Z 노영훈(#1868) Park (BOI16_park) C++11
0 / 100
 407 ms 37316 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 MX=500010, 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(to+1)==fr) swap(to,fr);
    if(f(fr+1)==to) return go(fr, f(fr+2));
    if(f(fr+2)==to) return go(fr, f(fr+2)) && go(f(fr+1), f(fr+3));
    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 gap(int a, int b){
    // sqrt???
    if(b<=n)
        return 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() && stuck(V[i], P[j+1].second)){
            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

# Verdict Execution time Memory Grader output
1 Correct 393 ms 37312 KB Output is correct
2 Incorrect 407 ms 37316 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 171 ms 37316 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 393 ms 37312 KB Output is correct
2 Incorrect 407 ms 37316 KB Output isn't correct
3 Halted 0 ms 0 KB -