| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 349429 |
2021-01-17T15:30:59 Z |
mp007mp |
Park (BOI16_park) |
C++14 |
|
327 ms |
876 KB |
#include<bits/stdc++.h>
#define X second
#define Y first
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pii;
const ll maxn=3021;
ll inf = 1000ll*1000*1000*1000;
ll n,m,w,h;
pii cen[maxn];
ll r[maxn];
ll mark[maxn][4];
vector<ll> daste[4][4];
void seprate(ll u,ll v,ll mmkn[4][4]){
bool exsist[4];
fill(exsist,exsist+4,0);
for(ll i:daste[u][v]){
exsist[i]=1;
}
for(ll i=0;i<4;i++){
for(ll j=i+1;j<4;j++){
if((exsist[i] && !exsist[j]) || (exsist[j] && !exsist[i])){
mmkn[i][j]=0;
mmkn[j][i]=0;
}
}
}
return;
}
ll dist(pii a,pii b){
ll res = 0;
ll tmp = abs(a.X-b.X);
tmp *= tmp;
res += tmp;
tmp = abs(a.Y-b.Y);
tmp *= tmp;
res += tmp;
return res;
}
ll dist(ll a,ll b,ll c){
ll tmp = a+b+c+c;
tmp *= tmp;
return tmp;
}
bool vasl(ll u,ll v,ll x){
if(dist(cen[u],cen[v]) < dist(r[u],r[v],x)){
return true;
}else{
return false;
}
}
void dfs(ll v,ll c,ll x){
for(ll i=1;i<=n;i++){
if(!mark[i][c] && vasl(i,v,x)){
mark[i][c]=1;
dfs(i,c,x);
}
}
}
bool check(ll s,ll t,ll x){
ll mmkn[4][4];
for(ll i=0;i<4;i++){
fill(mark[i],mark[i]+maxn,0);
fill(mmkn[i],mmkn[i]+4,1);
}
for(ll i=1;i<=n;i++){
if(!mark[i][0] && cen[i].Y-r[i]<x*2){
mark[i][0]=1;
dfs(i,0,x);
}
}
for(ll i=1;i<=n;i++){
if(!mark[i][1] && w-cen[i].X-r[i]<x*2){
mark[i][1]=1;
dfs(i,1,x);
}
}
for(ll i=1;i<=n;i++){
if(!mark[i][2] && h-cen[i].Y-r[i]<x*2){
mark[i][2]=1;
dfs(i,2,x);
}
}
for(ll i=1;i<=n;i++){
if(!mark[i][3] && cen[i].X-r[i]<x*2){
mark[i][3]=1;
dfs(i,3,x);
}
}
for(ll i=1;i<=n;i++){
for(ll v=0;v<4;v++){
for(ll u=v+1;u<4;u++){
if(mark[i][v] && mark[i][u]){
seprate(v,u,mmkn);
}
}
}
}
return mmkn[s][t];
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>w>>h;
for(ll i=1;i<=n;i++){
cin>>cen[i].X>>cen[i].Y>>r[i];
}
for(ll i=0;i<3;i++){
daste[i][i+1].push_back(i+1);
}
daste[0][3].push_back(0);
daste[0][2].push_back(1);
daste[0][2].push_back(2);
daste[1][3].push_back(2);
daste[1][3].push_back(3);
ll mmkn[4][4];
for(ll i=0;i<4;i++){
fill(mmkn[i],mmkn[i]+4,0);
}
for(ll i=0;i<4;i++){
for(ll j=i+1;j<4;j++){
ll l=-1,r=min(h,w)/4 + 100;
while(r-l>1){
ll mid = (r+l) >> 1;
if(check(i,j,mid)){
l = mid;
}else{
r = mid;
}
}
mmkn[i][j] = l;
mmkn[j][i] = l;
}
mmkn[i][i]=inf;
}
/*for(ll i=0;i<4;i++){
for(ll j=0;j<4;j++){
cout<<mmkn[i][j]<<" ";
}cout<<"\n";
}*/
if(m==1){
ll ent,shoa;
cin>>shoa>>ent;
ent--;
for(ll i=0;i<4;i++){
if(i==ent){
cout<<i+1;
continue;
}
if(check(i,ent,shoa))cout<<i+1;
}cout<<"\n";
return 0;
}
while(m--){
ll ent,shoa;
cin>>shoa>>ent;
ent--;
for(ll i=0;i<4;i++){
if(mmkn[ent][i] >= shoa)cout<<i+1;
}cout<<"\n";
}
/*for(int i=1;i<=n;i++){
for(int j=0;j<4;j++){
cout<<mark[i][j]<<" ";
}cout<<"\n";
}*/
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
327 ms |
696 KB |
Output is correct |
| 2 |
Incorrect |
273 ms |
620 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
61 ms |
748 KB |
Output is correct |
| 2 |
Correct |
70 ms |
876 KB |
Output is correct |
| 3 |
Correct |
55 ms |
748 KB |
Output is correct |
| 4 |
Correct |
67 ms |
748 KB |
Output is correct |
| 5 |
Correct |
58 ms |
876 KB |
Output is correct |
| 6 |
Correct |
65 ms |
748 KB |
Output is correct |
| 7 |
Correct |
36 ms |
748 KB |
Output is correct |
| 8 |
Correct |
34 ms |
748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
327 ms |
696 KB |
Output is correct |
| 2 |
Incorrect |
273 ms |
620 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
