oj.uz

Submission #86567

# Submission time Handle Problem Language Result Execution time Memory
86567 2018-11-26T15:27:48 Z sjhuang26 Park (BOI16_park) C++14
0 / 100
 1148 ms 23340 KB 
#include<iostream>
#include<string>
#include<cmath>
#include<bits/stdc++.h>
using namespace std;
int p[2004],h[2004],x[100000],y[100000],r[100000],N,M,W,H,cut[4][4];
double dist[2000][2000];
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]=b;
    else if(h[a]>h[b])p[b]=a;
    else p[a]=b,++h[b];
  }
}
bool sameset(int a,int b){
  return getp(a)==getp(b);
}
bool works(int n,int u,int v){
  //cout<<n<<' '<<u<<' '<<v<<endl;
  for(int i=0;i<N+4;++i)h[i]=1,p[i]=i;
  for(int i=0;i<N;++i){
    for(int j=i+1;j<N;++j){
      if(dist[i][j]+0.000001<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(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin>>N>>M>>W>>H;
  for(int i=0;i<N;++i)cin>>x[i]>>y[i]>>r[i];
  // precompute distances
  for(int i=0;i<N;++i)for(int j=i+1;j<N;++j){
    dist[i][j]=sqrt((double)(x[i]-x[j]+y[i]-y[j])*(x[i]-x[j]-y[i]+y[j]));
  }
  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;
}

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1148 ms 23160 KB Output is correct
2 Incorrect 1088 ms 23340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

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

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1148 ms 23160 KB Output is correct
2 Incorrect 1088 ms 23340 KB Output isn't correct
3 Halted 0 ms 0 KB -