| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1192788 | Godgift42 | Park (BOI16_park) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
vector<int> rt;
vector<int> sz;
int find(int u){
if(u!=rt[u])rt[u]=find(rt[u]);
return rt[u];
}
void unite(int u, int v){
u=find(u);
v=find(v);
if(u!=v){
if(sz[u]>sz[v]){
rt[v]=u;
sz[u]+=sz[v];
}
else{
rt[u]=v;
sz[v]+=sz[u];
}
}
}
int main(){
int n,m;
cin >> n >> m;
int w,h;
cin >> w >> h;
vector<vector<int>>tr(n,vector<int>(3));
for(int i=0;i<n;i++){
cin >> tr[i][0] >> tr[i][1] >> tr[i][2];
}
vector<pair<int,pair<int,int>>> p(m);
for(int i=0;i<m;i++){
cin >> p[i].first >> p[i].second.first;
p[i].second.second=i;
}
vector<pair<int,pair<int,int>>> el;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i==j)continue;
int d=floor(sqrt((tr[i][0]-tr[j][0])*(tr[i][0]-tr[j][0])+(tr[i][1]-tr[j][1])*(tr[i][1]-tr[j][1]))-tr[i][2]-tr[j][2]);
el.push_back({d,{i,j}});
}
int d=floor(tr[i][1]-tr[i][2]);
el.push_back({d,{i,n}});
d=floor(w-tr[i][0]-tr[i][2]);
el.push_back({d,{i,n+1}});
d=floor(h-tr[i][1]-tr[i][2]);
el.push_back({d,{i,n+2}});
d=floor(tr[i][0]-tr[i][2]);
el.push_back({d,{i,n+3}});
}
sort(el.begin(),el.end());
rt.resize(n+4);
for(int i=0;i<n+4;i++)rt[i]=i;
sz.resize(n+4,1);
sort(p.begin(),p.end());
vector<vector<int>> ans(m);
int j=0;
for(int i=0;i<m;i++){
while(j<el.size() and el[j].first<2*p[i].first){
unite(el[j].second.first,el[j].second.second);
j++;
}
ans[p[i].second.second].push_back(p[i].second.first);
if(p[i].second.first==1){
if(find(n)==find(n+3))continue;
if(find(n+1)!=find(n+3) and find[n+2)!=find(n+3))ans[p[i].second.second].push_back(4);
if(find(n+1)!=find(n) and find(n+2)!=find(n))ans[p[i].second.second].push_back(2);
if(find(n+1)!=find(n+2) and find(n+2)!=find(n) and find(n+1)!=find(n+3))ans[p[i].second.second].push_back(3);
}
else if(p[i].second.first==2){
if(find(n+1)==find(n))continue;
if(find(n+1)!=find(n+2) and find(n+1)!=find(n+3))ans[p[i].second.second].push_back(3);
if(find(n+3)!=find(n) and find(n+2)!=find(n))ans[p[i].second.second].push_back(1);
if(find(n+3)!=find(n+2) and find(n+2)!=find(n) and find(n+1)!=find(n+3))ans[p[i].second.second].push_back(4);
}
else if(p[i].second.first==3){
if(find(n+1)==find(n+2))continue;
if(find(n+1)!=find(n+3) and find(n)!=find(n+1))ans[p[i].second.second].push_back(2);
if(find(n+2)!=find(n+3) and find(n+2)!=find(n))ans[p[i].second.second].push_back(4);
if(find(n)!=find(n+3) and find(n+2)!=find(n) and find(n+1)!=find(n+3))ans[p[i].second.second].push_back(1);
}
else{
if(find(n+2)==find(n+3))continue;
if(find(n+1)!=find(n+3) and find(n)!=find(n+3))ans[p[i].second.second].push_back(1);
if(find(n+1)!=find(n+2) and find(n+2)!=find(rt[n]))ans[p[i].second.second].push_back(3);
if(find(n+1)!=find(n) and find(n+2)!=find(n) and find(n+1)!=find(n+3))ans[p[i].second.second].push_back(2);
}
}
for(int i=0;i<m;i++){
sort(ans[i].begin(),ans[i].end());
for(auto o:ans[i])cout <<o;
cout << "\n";
}
}