oj.uz

Submission #85826

# Submission time Handle Problem Language Result Execution time Memory
85826 2018-11-21T17:46:10 Z sjhuang26 Park (BOI16_park) C++14
0 / 100
 2500 ms 1836 KB 
#include<iostream>
#include<string>
#include<cmath>
using namespace std;
int p[2004],h[2004],x[100000],y[100000],r[100000],N,M,W,H,cut[4][4];
int getp(int n){
  return p[n]==n?n:p[n]=getp(p[n]);
}
void unionset(int a,int b){
  a=getp(a);b=getp(b);
  if(a!=b){
    if(h[a]<h[b])p[a]=p[b];
    else if(h[a]>h[b])p[b]=p[a];
    else p[a]=p[b],++h[b];
  }
}
bool sameset(int a,int b){
  return getp(a)==getp(b);
}
bool works(int n,int u,int v){
  for(int i=0;i<N+4;++i)h[i]=1,p[i]=i;
  for(int i=0;i<N;++i){
    for(int j=0;j<N;++j)if(i!=j){
      double dist=sqrt((double)(x[i]-x[j]+y[i]-y[j])*(x[i]-x[j]-y[i]+y[j]));
      if(dist<r[i]+r[j]+2*n)unionset(i,j);
    }
    if(H-y[i]<2*n)unionset(i,N+2);
    if(y[i]<2*n)unionset(i,N);
    if(W-x[i]<2*n)unionset(i,N+1);
    if(x[i]<2*n)unionset(i,N+3);
  }
  if(sameset(N+0,N+3)&&(u==0||v==0))return 0;
  if(sameset(N+1,N+0)&&(u==1||v==1))return 0;
  if(sameset(N+2,N+1)&&(u==2||v==2))return 0;
  if(sameset(N+3,N+2)&&(u==3||v==3))return 0;
  if(sameset(N+0,N+2)&&!(u==0&&v==3||u==1&&v==2))return 0;
  if(sameset(N+1,N+3)&&!(u==0&&v==1||u==2&&v==3))return 0;
  return 1;
}
int main(){
  cin>>N>>M>>W>>H;
  for(int i=0;i<N;++i)cin>>x[i]>>y[i]>>r[i];
  for(int i=0;i<4;++i)for(int j=0;j<4;++j)if(i<j){
    int maxworks=-1,lo=0,hi=1e9;
    while(lo<=hi){
      int md=(lo+hi)/2;
      if(works(md,i,j)){
        maxworks=md;
        lo=md+1;
      }else{
        hi=md-1;
      }
    }
    cut[i][j]=maxworks;
  }else if(i>j)cut[i][j]=cut[j][i];
  else cut[i][j]=1e9;
  for(int i=0;i<M;++i){
    int v,e;cin>>v>>e;--e;
    string res="";
    for(int j=0;j<4;++j)if(cut[e][j]>=v){
      res+='1'+j;
    }
    cout<<res<<"\n";
  }
  return 0;
}

Compilation message

park.cpp: In function 'bool works(int, int, int)':
park.cpp:36:30: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if(sameset(N+0,N+2)&&!(u==0&&v==3||u==1&&v==2))return 0;
                          ~~~~^~~~~~
park.cpp:37:30: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if(sameset(N+1,N+3)&&!(u==0&&v==1||u==2&&v==3))return 0;
                          ~~~~^~~~~~

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2556 ms 376 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 341 ms 1836 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2556 ms 376 KB Time limit exceeded
2 Halted 0 ms 0 KB -