| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 377945 |
2021-03-15T15:20:13 Z |
YJU |
Park (BOI16_park) |
C++14 |
|
1174 ms |
133588 KB |
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll N=1e5+10;
const ll MOD=1e9+7;
const ld pi=3.14159265359;
const ll INF=(1LL<<60);
const ld eps=1e-12;
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define X first
#define Y second
#define pb push_back
#define mp make_pair
#define setp setprecision
#define lwb lower_bound
#define SZ(a) (ll)a.size()
#define SQ(_a) ((_a)*(_a))
ll sz[N],dir[N];
ll find(ll nd){
return (dir[nd]==nd?nd:dir[nd]=find(dir[nd]));
}
void Union(ll nda,ll ndb){
nda=find(nda);ndb=find(ndb);
if(nda==ndb)return ;
if(sz[nda]>sz[ndb])swap(nda,ndb);
sz[ndb]+=sz[nda];
dir[nda]=ndb;
}
bool is(ll nda,ll ndb){
return (find(nda)==find(ndb));
}
ll tx[N],ty[N],tr[N];
ll ans[N],qe[N],qr[N];
ll m,W,H,n;
ll side[100][20];
ll ve[40],ho[40];
vector<pair<ld,pll> > query,event;
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>m;
//prepare
REP1(i,N-1)dir[i]=i,sz[i]=1;
side[0][0]=n+4,side[0][1]=n+3;
side[1][0]=n+3;side[1][1]=n+2;
side[2][0]=n+2;side[2][1]=n+1;
side[3][0]=n+1;side[3][1]=n+4;
ho[0]=ho[1]=(1<<2)|(1<<3);
ho[2]=ho[3]=(1<<1)|(1<<0);
ve[0]=ve[3]=(1<<2)|(1<<1);
ve[1]=ve[2]=(1<<0)|(1<<3);
//endprepare
cin>>W>>H;
/*
n+1
-------------
|3 2|
n+4 |0 1|n+2
-------------
n+3
*/
REP1(i,n){
cin>>tx[i]>>ty[i]>>tr[i];
}
REP1(i,n)REP1(j,n){
event.pb(mp((ld)sqrt((tx[i]-tx[j])*(tx[i]-tx[j])+(ty[i]-ty[j])*(ty[i]-ty[j]))-tr[i]-tr[j],mp(i,j)));
}
REP1(i,n){
event.pb(mp(ty[i]-tr[i],mp(i,n+3)));
event.pb(mp(H-ty[i]-tr[i],mp(i,n+1)));
event.pb(mp(tx[i]-tr[i],mp(i,n+4)));
event.pb(mp(W-tx[i]-tr[i],mp(i,n+2)));
}
REP1(i,m){
cin>>qr[i]>>qe[i];
query.pb(mp(2*qr[i],mp(qe[i],i)));
}
sort(event.begin(),event.end());
sort(query.begin(),query.end());
for(int i=0,j=0;i<SZ(query);i++){
while(j<SZ(event)&&event[j].X<query[i].X){
Union(event[j].Y.X,event[j].Y.Y);
++j;
}
ll ent=query[i].Y.X-1,id=query[i].Y.Y;
if(is(n+2,n+4)){
ans[id]|=ho[ent];
}
if(is(n+1,n+3)){
ans[id]|=ve[ent];
}
if(is(side[ent][0],side[ent][1])){
ans[id]|=(((1<<4)-1)^(1<<ent));
}
ll rent=(ent+2)%4;
if(is(side[rent][0],side[rent][1])){
ans[id]|=(1<<rent);
}
}
REP1(i,m){
REP(j,4)if(((ans[i]>>j)&1)==0)cout<<j+1;
cout<<"\n";
}
return 0;
}
/*
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 |
Correct |
1120 ms |
133460 KB |
Output is correct |
| 2 |
Incorrect |
1174 ms |
133588 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
77 ms |
9312 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1120 ms |
133460 KB |
Output is correct |
| 2 |
Incorrect |
1174 ms |
133588 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
