Submission #484674

#	Time	Username	Problem	Language	Result	Execution time	Memory
484674		phamhoanghiep	Park (BOI16_park)	C++14	100 / 100	377 ms	57772 KiB

park

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> ii;
const int maxn=2005;
const int maxm=1e5+5;
vector<int> ans[maxm];
int n,m;
int w,h;
struct pt{
    int x;
    int y;
    int r;
} trees[maxn];
int pset[maxn];
int sz[maxn];
void init() {
    for(int i=1 ; i<=n ; i++) {
        pset[i]=i;
        sz[i]=1;
    }
}
vector<pair<double,ii>> edges;
vector<pair<double,ii>> queries;
int find_set(int s) {
    if(pset[s]==s) return s;
    return pset[s]=find_set(pset[s]);
}
bool same_set(int u, int v) {
    return find_set(u)==find_set(v);
}
void union_set(int u, int v) {
    u=find_set(u); v=find_set(v);
    if(u==v) return;
    if(sz[u]>sz[v]) swap(u,v);
    pset[u]=v;
    sz[v]+=sz[u];
}
signed main() {
    cin>>n>>m;
    cin>>w>>h;
    n+=4;
    init();
    for(int i=5 ; i<=n ; i++) {
        cin>>trees[i].x>>trees[i].y>>trees[i].r;
        edges.push_back(make_pair((double)(trees[i].x-trees[i].r),ii(1,i)));
        edges.push_back(make_pair((double)(trees[i].y-trees[i].r),ii(2,i)));
        edges.push_back(make_pair((double)(w-trees[i].x-trees[i].r),ii(3,i)));
        edges.push_back(make_pair((double)(h-trees[i].y-trees[i].r),ii(4,i)));
    }
    for(int i=5 ; i<=n ; i++) {
        for(int j=i+1 ; j<=n ; j++) {
            edges.push_back(make_pair(sqrt((trees[i].x-trees[j].x)*(trees[i].x-trees[j].x)+(trees[i].y-trees[j].y)*(trees[i].y-trees[j].y))-trees[i].r-trees[j].r,ii(i,j)));
        }
    }
    sort(edges.begin(),edges.end());
    for(int i=1 ; i<=m ; i++) {
        int r;
        int st;
        cin>>r>>st;
        queries.push_back(make_pair(2*r,ii(st,i)));
    }
    sort(queries.begin(),queries.end());
    int cur_id=0;
    int sz=edges.size();
    for(int i=0 ; i<m ; i++) {
        while(cur_id<sz&&edges[cur_id].first<queries[i].first) {
            union_set(edges[cur_id].second.first,edges[cur_id].second.second);
            //cout<<"edges "<<cur_id<<" = "<<edges[cur_id].first<<" "<<edges[cur_id].second.first<<" "<<edges[cur_id].second.second<<endl;
            cur_id++;
        }
        int st=queries[i].second.first;
        int id=queries[i].second.second;
        ans[id].push_back(st);
        if(st==1) {
            if((!same_set(2,1))&&(!same_set(2,3))&&(!same_set(2,4))) ans[id].push_back(2);
            if((!same_set(2,1))&&(!same_set(1,3))&&(!same_set(2,4))&&(!same_set(3,4))) ans[id].push_back(3);
            if((!same_set(2,1))&&(!same_set(1,3))&&(!same_set(1,4))) ans[id].push_back(4);
        }
        if(st==2) {
            if((!same_set(2,1))&&(!same_set(2,3))&&(!same_set(2,4))) ans[id].push_back(1);
            if((!same_set(3,1))&&(!same_set(2,3))&&(!same_set(3,4))) ans[id].push_back(3);
            if((!same_set(2,3))&&(!same_set(1,3))&&(!same_set(1,4))&&(!same_set(2,4))) ans[id].push_back(4);
        }
        if(st==3) {
            if((!same_set(2,1))&&(!same_set(1,3))&&(!same_set(2,4))&&(!same_set(3,4))) ans[id].push_back(1);
            if((!same_set(2,3))&&(!same_set(1,3))&&(!same_set(3,4))) ans[id].push_back(2);
            if((!same_set(4,1))&&(!same_set(4,3))&&(!same_set(2,4))) ans[id].push_back(4);
        }
        if(st==4) {
            if((!same_set(2,1))&&(!same_set(1,3))&&(!same_set(1,4))) ans[id].push_back(1);
            if((!same_set(4,1))&&(!same_set(1,3))&&(!same_set(2,4))&&(!same_set(3,2))) ans[id].push_back(2);
            if((!same_set(2,4))&&(!same_set(4,3))&&(!same_set(1,4))) ans[id].push_back(3);
        }
    }
    for(int i=1 ; i<=m ; i++) {
        sort(ans[i].begin(),ans[i].end());
        for(int u: ans[i]) cout<<u;
        cout<<'\n';
    }
}
/*
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: 27 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42