| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1105973 |
2024-10-28T15:52:42 Z |
doducanh |
Park (BOI16_park) |
C++14 |
|
416 ms |
54260 KB |
///breaker
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#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
{
double dodai;
ii a,b;
bool operator <(const edges &b){
return dodai<b.dodai;
}
};
int n,m,w,h;
vector<edges>ed;
double dis(int x1,int y1,int x2,int y2)
{
return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}
void add(int x1,int y1,int x2,int y2,int r1,int r2)
{
double 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].se>>a[i].fi>>a[i].r;
cc[(ii){0,a[i].se}]=0;
cc[(ii){a[i].fi,w}]=1;
cc[(ii){h,a[i].se}]=2;
cc[(ii){a[i].fi,0}]=3;
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,w,a[i].r,0);
add(a[i].fi,a[i].se,h,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
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
416 ms |
54260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
4652 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
416 ms |
54260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
