Submission #1105985

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105985		doducanh	Park (BOI16_park)	C++14	0 / 100	582 ms	89252 KiB

park

///breaker
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define double long double
#define fi first
#define se second
#define ii pair<int,int>
#define mp make_pair
#define in(x) freopen(x,"r",stdin)
#define out(x) freopen(x,"w",stdout)
#define bit(x,i) ((x>>i)&1)
#define lc (id<<1)
#define rc ((id<<1)^1)
const int maxn=4005;
const int maxm=1e5+7;
int sz[2*maxm];
int r[2*maxm];
bool ok[maxm][4];
struct tree
{
    int fi,se,r;
}a[maxn];
struct nguoi
{
    int id,r,e;
}b[maxm];
struct edges
{
    ll dodai;
    ii a,b;
    bool operator <(const edges &b){
        return dodai<b.dodai;
    }
};
int n,m,w,h;
vector<edges>ed;
long long dis(int x1,int y1,int x2,int y2)
{
    return sqrt(1ll*(x2-x1)*(x2-x1)+1ll*(y2-y1)*(y2-y1));
}
void add(int x1,int y1,int x2,int y2,int r1,int r2)
{
    long long dist=dis(x1,y1,x2,y2)-r1-r2;
    ii a={x1,y1};
    ii b={x2,y2};
    ed.push_back({dist,a,b});
}
int Find(int u)
{
    return ((u==r[u])?u:r[u]=Find(r[u]));
}
map<ii,int>cc;
bool con[4][4];
bool ans[maxm][4];
bool check(int x)
{
    return con[x][((x-1<0)?3:x-1)];
}
void Union(int a,int b)
{
    a=Find(a);
    b=Find(b);
    if(a==b)return;
    if(sz[a]<sz[b])swap(a,b);
    sz[a]+=sz[b];
    r[b]=a;
}
void sol(void){
    cin>>n>>m;
    cin>>w>>h;
    for(int i=1;i<=n;i++){
        cin>>a[i].fi>>a[i].se>>a[i].r;
        cc[(ii){0,a[i].se}]=3;
        cc[(ii){a[i].fi,h}]=2;
        cc[(ii){w,a[i].se}]=1;
        cc[(ii){a[i].fi,0}]=0;
        add(a[i].fi,a[i].se,0,a[i].se,a[i].r,0);
        add(a[i].fi,a[i].se,a[i].fi,h,a[i].r,0);
        add(a[i].fi,a[i].se,w,a[i].se,a[i].r,0);
        add(a[i].fi,a[i].se,a[i].fi,0,a[i].r,0);

    }
    int cnt=4;
    for(int i=1;i<=n;i++){
        cc[(ii){a[i].fi,a[i].se}]=cnt++;
        for(int j=i+1;j<=n;j++){
            add(a[i].fi,a[i].se,a[j].fi,a[j].se,a[i].r,a[j].r);
        }
    }
    for(int i=0;i<=cnt;i++){
        r[i]=i;
        sz[i]=1;
    }
    for(int i=1;i<=m;i++){
        cin>>b[i].r>>b[i].e;
        b[i].e--;
        b[i].r=2*b[i].r;
        b[i].id=i;
    }
    sort(b+1,b+m+1,[&](const nguoi &a,const nguoi &b){
         return a.r<b.r;
    });
    for(int i=1;i<=m;i++){
        for(int j=0;j<4;j++){
            ok[i][j]=1;
        }
    }
    sort(ed.begin(),ed.end());
    int p=1;
    for(auto v:ed){
        while(p<=m&&(double)b[p].r<=(double)v.dodai){
            nguoi curr=b[p];
            for(int i=0;i<4;i++){
                con[i][i]=true;
                for(int j=i+1;j<4;j++){
                    con[i][j]=(Find(i)==Find(j));
                    con[j][i]=con[i][j];
                }
            }
            for(int i=0;i<4;i++){
                if(curr.e==i)continue;
                if(check(curr.e)||check(i)){
                    ok[curr.id][i]=0;
                    continue;
                }
                bool ngang=con[1][3];
                bool doc=con[0][2];
                if(abs(curr.e-i)==1){
                    if(doc){
                        ok[curr.id][i]=0;
                        continue;
                    }
                }
                else if(abs(curr.e-i)==2){
                    if(doc||ngang){
                        ok[curr.id][i]=0;
                        continue;
                    }
                }
                else if(ngang){
                    ok[curr.id][i]=0;
                    continue;
                }
            }
            p++;
        }
        Union(cc[v.a],cc[v.b]);
    }
    for(int i=1;i<=m;i++){
        for(int j=0;j<4;j++){
            if(ok[i][j]){
                cout<<j+1;
            }
        }
        cout<<"\n";
    }
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    while(t--){
        sol();
    }
    // you should actually read the stuff at the bottom
    return 0;
}
/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */
//5 3
//16 11
//11 8 1
//6 10 1
//7 3 2
//10 4 1
//15 5 1
//1 1
//2 2
//2 1

• Subtask 1: 0 / 27
• Subtask 2: 0 / 31
• Subtask 3: 0 / 42