oj.uz

Submission #63862

# Submission time Handle Problem Language Result Execution time Memory
63862 2018-08-03T05:31:04 Z 노영훈(#1868) Park (BOI16_park) C++11
0 / 100
 9 ms 728 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
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 circ{
    int x, y, r;
    void scan(){ cin>>x>>y>>r; }
} T[2010];

//   3
// 1   2
//   4
inline bool go(int a, int b){ return find(n+a)!=find(n+b); }

bool one(int e){
    if(e==1) return true;
    if(!go(1,4)) return false;
    if(e==2) return go(2,4) && go(3,4);
    if(e==3) return go(2,3) && go(3,4) && go(1,2);
    if(e==4) return go(1,3) && go(1,2);
    return false;
}
bool two(int e){
    if(e==2) return true;
    if(!go(2,4)) return false;
    if(e==1) return go(1,4) && go(3,4);
    if(e==3) return go(2,3) && go(1,2);
    if(e==4) return go(1,3) && go(1,2) && go(3,4);
    return false;
}
bool thr(int e){
    if(e==3) return true;
    if(!go(2,3)) return false;
    if(e==1) return go(1,4) && go(3,4) && go(1,2);
    if(e==2) return go(2,4) && go(1,2);
    if(e==4) return go(1,3) && go(3,4);
    return false;
}
bool fou(int e){
    if(e==4) return true;
    if(!go(1,3)) return false;
    if(e==1) return go(1,4) && go(1,2);
    if(e==2) return go(2,4) && go(3,4) && go(1,2);
    if(e==3) return go(2,3) && go(3,4);
    return false;
}

struct man{
    int r, e;
    void scan(){
        cin>>r>>e;
    }
    void show(){
        vector<int> ans;
        if(one(e)) ans.push_back(1);
        if(two(e)) ans.push_back(2);
        if(thr(e)) ans.push_back(3);
        if(fou(e)) ans.push_back(4);
        for(int x:ans) cout<<x;
        cout<<'\n';
    }
} V[100010];

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

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

bool stuck(circ &a, circ &b, man &k){
    return dist(a,b)<sq(2*k.r+a.r+b.r);
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m>>w>>h;
    assert(m==1);
    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();

    for(int i=1; i<=n; i++) for(int j=i+1; j<=n; j++)
        if(stuck(T[i], T[j], V[1])) unite(i,j);
    
    //   3
    // 1   2
    //   4
    for(int i=1; i<=n; i++){
        if(T[i].x-0<T[i].r+2*V[1].r) unite(i,n+1);
        if(w-T[i].x<T[i].r+2*V[1].r) unite(i,n+2);
        if(T[i].y-0<T[i].r+2*V[1].r) unite(i,n+3);
        if(h-T[i].y<T[i].r+2*V[1].r) unite(i,n+4);
    }

    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 9 ms 376 KB Output is correct
2 Incorrect 9 ms 488 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 728 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 376 KB Output is correct
2 Incorrect 9 ms 488 KB Output isn't correct
3 Halted 0 ms 0 KB -