oj.uz

Submission #63912

# Submission time Handle Problem Language Result Execution time Memory
63912 2018-08-03T06:53:08 Z 노영훈(#1868) Park (BOI16_park) C++11
100 / 100
 916 ms 39588 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
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)>>1;
        if(m*m<=x) s=m;
        else e=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-T[a].r;
    if(b-n==2) return w-T[a].x-T[a].r;
    if(b-n==3) return h-T[a].y-T[a].r;
    if(b-n==4) return T[a].x-T[a].r;
    assert(false);
}

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()-1 && 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
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 759 ms 37316 KB Output is correct
2 Correct 809 ms 37424 KB Output is correct
3 Correct 865 ms 37544 KB Output is correct
4 Correct 779 ms 37544 KB Output is correct
5 Correct 762 ms 37544 KB Output is correct
6 Correct 748 ms 37596 KB Output is correct
7 Correct 749 ms 37596 KB Output is correct
8 Correct 731 ms 37596 KB Output is correct
9 Correct 6 ms 37596 KB Output is correct
10 Correct 6 ms 37596 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 37596 KB Output is correct
2 Correct 129 ms 37596 KB Output is correct
3 Correct 150 ms 37596 KB Output is correct
4 Correct 120 ms 37596 KB Output is correct
5 Correct 115 ms 37596 KB Output is correct
6 Correct 132 ms 37596 KB Output is correct
7 Correct 123 ms 37596 KB Output is correct
8 Correct 161 ms 37596 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 759 ms 37316 KB Output is correct
2 Correct 809 ms 37424 KB Output is correct
3 Correct 865 ms 37544 KB Output is correct
4 Correct 779 ms 37544 KB Output is correct
5 Correct 762 ms 37544 KB Output is correct
6 Correct 748 ms 37596 KB Output is correct
7 Correct 749 ms 37596 KB Output is correct
8 Correct 731 ms 37596 KB Output is correct
9 Correct 6 ms 37596 KB Output is correct
10 Correct 6 ms 37596 KB Output is correct
11 Correct 159 ms 37596 KB Output is correct
12 Correct 129 ms 37596 KB Output is correct
13 Correct 150 ms 37596 KB Output is correct
14 Correct 120 ms 37596 KB Output is correct
15 Correct 115 ms 37596 KB Output is correct
16 Correct 132 ms 37596 KB Output is correct
17 Correct 123 ms 37596 KB Output is correct
18 Correct 161 ms 37596 KB Output is correct
19 Correct 916 ms 39588 KB Output is correct
20 Correct 855 ms 39588 KB Output is correct
21 Correct 912 ms 39588 KB Output is correct
22 Correct 904 ms 39588 KB Output is correct
23 Correct 899 ms 39588 KB Output is correct
24 Correct 883 ms 39588 KB Output is correct