| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 484673 |
2021-11-05T02:58:56 Z |
phamhoanghiep |
Park (BOI16_park) |
C++14 |
|
313 ms |
52108 KB |
#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);
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';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
287 ms |
52108 KB |
Output is correct |
| 2 |
Incorrect |
313 ms |
52072 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
104 ms |
11624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
287 ms |
52108 KB |
Output is correct |
| 2 |
Incorrect |
313 ms |
52072 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
