| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 236414 |
2020-06-02T05:38:37 Z |
alishahali1382 |
Park (BOI16_park) |
C++14 |
|
2500 ms |
35192 KB |
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;
const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=2010, LOG=20;
ll n, m, k, w, h, x, y, t, r, s, cnt;
ll X[MAXN], Y[MAXN], R[MAXN];
int par[MAXN];
pair<ll, pii> E[MAXN*MAXN/2];
ll ans12=-1, ans13=-1, ans14=-1, ans23=-1, ans24=-1, ans34=-1;
int getpar(int x){
if (par[x]==x) return x;
return par[x]=getpar(par[x]);
}
void join(int x, int y){
par[getpar(x)]=getpar(y);
}
inline void upd(ll &x, ll d){
if (x==-1) x=d;
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
cin>>n>>m>>w>>h;
E[cnt++]={(w), {n+2, n+4}};
E[cnt++]={(h), {n+1, n+3}};
for (int i=1; i<=n; i++){
cin>>X[i]>>Y[i]>>R[i];
E[cnt++]={((Y[i]-R[i])), {i, n+1}};
E[cnt++]={((w-X[i]-R[i])), {i, n+2}};
E[cnt++]={((h-Y[i]-R[i])), {i, n+3}};
E[cnt++]={((X[i]-R[i])), {i, n+4}};
}
for (int i=1; i<=n; i++) for (int j=i+1; j<=n; j++){
ll dx=X[i]-X[j], dy=Y[i]-Y[j], d=dx*dx+dy*dy;
E[cnt++]={((ceil(sqrt(d+.1))-R[i]-R[j])), {i, j}};
}
sort(E, E+cnt);
//reverse(E, E+cnt);
iota(par, par+MAXN, 0);
ll shit=226020958;
for (int i=0; i<cnt; i++){
int x=E[i].second.first, y=E[i].second.second;
ll d=E[i].first;
join(x, y);
if (d<shit) {cerr<<d<<" : ";debug2(x, y)}
if (getpar(n+1)==getpar(n+2)){
upd(ans12, d);
upd(ans24, d);
upd(ans23, d);
}
if (getpar(n+1)==getpar(n+3)){
upd(ans12, d);
upd(ans13, d);
upd(ans24, d);
upd(ans34, d);
}
if (getpar(n+1)==getpar(n+4)){
upd(ans12, d);
upd(ans13, d);
upd(ans14, d);
}
if (getpar(n+2)==getpar(n+3)){
upd(ans13, d);
upd(ans23, d);
upd(ans34, d);
}
if (getpar(n+2)==getpar(n+4)){
upd(ans13, d);
upd(ans23, d);
upd(ans14, d);
upd(ans24, d);
}
if (getpar(n+3)==getpar(n+4)){
upd(ans14, d);
upd(ans24, d);
upd(ans34, d);
}
}
debug(ans34-shit)
while (m--){
cin>>r>>s;
r*=2;
if (s==1){
cout<<"1";
if (r<ans12) cout<<"2";
if (r<ans13) cout<<"3";
if (r<ans14) cout<<"4";
}
if (s==2){
if (r<ans12) cout<<"1";
cout<<"2";
if (r<ans23) cout<<"3";
if (r<ans24) cout<<"4";
}
if (s==3){
if (r<ans13) cout<<"1";
if (r<ans23) cout<<"2";
cout<<"3";
if (r<ans34) cout<<"4";
}
if (s==4){
if (r<ans14) cout<<"1";
if (r<ans24) cout<<"2";
if (r<ans34) cout<<"3";
cout<<"4";
}
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
8 1
1000000000 1000000000
200000000 384529926 2459575
400000000 269059852 2459575
400000000 499999960 2459575
600000000 384529886 2459575
600000000 615469994 2459575
800000000 499999920 2459575
400000000 38119745 2459575
597768045 995105726 2459576
113010479 3
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2592 ms |
35192 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
120 ms |
1272 KB |
Output is correct |
| 2 |
Correct |
159 ms |
2296 KB |
Output is correct |
| 3 |
Correct |
236 ms |
2264 KB |
Output is correct |
| 4 |
Correct |
123 ms |
2168 KB |
Output is correct |
| 5 |
Correct |
115 ms |
2300 KB |
Output is correct |
| 6 |
Correct |
249 ms |
2424 KB |
Output is correct |
| 7 |
Incorrect |
37 ms |
1792 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2592 ms |
35192 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
