oj.uz

Submission #568845

# Submission time Handle Problem Language Result Execution time Memory
568845 2022-05-26T09:13:54 Z codebuster_10 Park (BOI16_park) C++17
100 / 100
 546 ms 73304 KB 
#include <bits/stdc++.h>
#define int int64_t //be careful about this 

using namespace std;

#define vt vector 
#define ar array 
#define pr pair 

#define f first 
#define s second

#define pb push_back
#define eb emplace_back

#define fr(i,a,b) for(int i = a; i < b; ++i)
#define rf(i,a,b) for(int i = b-1; i >= a; --i)
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))

namespace IN{
  template<class T> void re(vector<T> &A);
  template<class S,class T> void re(pair<S,T> &A);
  template<class T,size_t N> void re(array<T,N> &A);

  template<class T> void re(T& x){ 
    cin >> x;}
  template<class H, class... T> void re(H& h, T&... t){ 
    re(h); re(t...);}

  template<class T> void re(vector<T> &A){ 
    for(auto& x : A) re(x);}
  template<class S,class T> void re(pair<S,T> &A){ 
      re(A.first); re(A.second);}
  template<class T,size_t N> void re(array<T,N> &A){
    for(int i = 0; i < N; ++i)  re(A[i]);}
}

namespace OUT{
  template<class T>
  void __p(const T& a){ cout<<a; }
  template<class T, class F>
  void __p(const pair<T, F>& a){ cout<<"{"; __p(a.first); cout<<","; __p(a.second); cout<<"}\n"; }
  template<class T, size_t N>
  void __p(const array<T,N>& a){ cout<<"{"; for(int i=0;i<N;++i)__p(a[i]),cout<<",}\n"[i+1==N]; }
  template<class T>
  void __p(const vector<T>& a){
    cout<<"{";for(auto it=a.begin();it<a.end();it++)__p(*it),cout<<",}\n"[it+1==a.end()]; }
  template<class T, class ...Arg>
  void __p(T a1, Arg ...a){__p(a1); __p(a...); }
  template<class Arg1>
  void __f(const char *s, Arg1 &&arg1){ cout<<s<<" : "; __p(arg1); cout<<endl; }
  template<class Arg1, class ... Args>
  void __f(const char *ss, Arg1 &&arg1, Args &&... args){
    int b=0,i=0; do{ if(ss[i]=='(') b++; if(ss[i]==')') b--; i++;}while(!(ss[i]==','&&b==0));
    const char *comma=ss+i; cout.write(ss,comma-ss)<<" : ";__p(arg1);cout<<" | ";__f(comma+1,args...);}
  #define trace(...) cout<<"Line:"<<__LINE__<<"  ", __f(#__VA_ARGS__, __VA_ARGS__)
}


namespace FUN{
  void IO(string s = ""){
    ios_base::sync_with_stdio(NULL); 
    cin.tie(nullptr); 
    cout.precision(20); 
    cout << fixed;
    if(!s.empty()){
      freopen((s+".in").c_str(),"r",stdin);
      freopen((s+".out").c_str(),"w",stdout);
    }
  }

  const auto start_time = chrono::high_resolution_clock::now();
  void output_run_time(){
    // will work for ac,cc||cf.
#ifndef ONLINE_JUDGE
    auto end_time = chrono::high_resolution_clock::now();
    chrono::duration<double> diff = end_time-start_time;
      cout << "\n\n\nTime Taken : " << diff.count();
#endif
  }

  template<class T> bool ckmin(T& a, const T& b){ 
    return b < a ? a = b, true : false; }
    
  template<class T> bool ckmax(T& a, const T& b){ 
    return a < b ? a = b, true : false; }

  mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  int my_rand(int L, int R){ 
    return uniform_int_distribution<int>(L,R)(rng); }
  
  template<class T> int sz(const T& x){ 
    return int(x.size()); }

  template<class T> int lb(const vector<T>& vec,const T& val){
    return int(lower_bound(vec.begin(), vec.end(),val) - vec.begin()); }

  template<class T> int ub(const vector<T>& vec,const T& val){
    return int(upper_bound(vec.begin(), vec.end(),val) - vec.begin()); }

  constexpr int  dx[4] = {1,0,-1,0};
  constexpr int  dy[4] = {0,1,0,-1};
  constexpr char dr[4] = {'D','R','U','L'};

  constexpr long long INFLL1 = 1e16, INFLL2 = 9e18;
  constexpr int INF = 2e9;

  template<class T>
  vector<T> V(int n,T val){
    return vector<T> (n,val);
  }

  template<class T>
  vector<vector<T>> V(int n,int m,T val){
    return vector<vector<T>> (n,vector<T> (m,val));
  }

  template<class T>
  vector<vector<vector<T>>> V(int n,int m,int k,T val){
    return vector<vector<vector<T>>> (n,vector<vector<T>> (m,vector<T> (k,val)));
  }
}


using namespace IN;
using namespace OUT;
using namespace FUN;




















struct DSU {
  int n;
  // root node: -1 * component size
  // otherwise: parent
  vector<int> parent_or_size;

  DSU(int n) : n(n), parent_or_size(n, -1) {}

  int merge(int a, int b){
    int x = leader(a), y = leader(b);
    if(x == y) 
      return x;
    if(-parent_or_size[x] < -parent_or_size[y]) 
      swap(x, y);
    parent_or_size[x] += parent_or_size[y];
    parent_or_size[y] = x;
    return x ;
  }

  bool same(int a, int b){
    return leader(a) == leader(b);
  }

  int leader(int a){
    if(parent_or_size[a] < 0) 
      return a;
    return parent_or_size[a] = leader(parent_or_size[a]);
  }

  int size(int a){
    return -parent_or_size[leader(a)];
  }
  
  vector<vector<int>> groups(){
    vector<int> leader_buf(n), group_size(n);
    for(int i = 0; i < n; i++){
      leader_buf[i] = leader(i);
      group_size[leader_buf[i]]++;
    }
    vector<vector<int>> result(n);
    for(int i = 0; i < n; i++){
      result[i].reserve(group_size[i]);
    }
    for(int i = 0; i < n; i++){
      result[leader_buf[i]].push_back(i);
    }
    result.erase(remove_if(result.begin(), result.end(),[&](const auto& v){return v.empty(); }),result.end());
    return result;
  }
};



signed main(){
  IO();
  
  int N,M,W,H;
  re(N,M,W,H);

  vt<int> X(N), Y(N), R(N);

  fr(i,0,N){
    re(X[i],Y[i],R[i]);
  }


  vt<pair<pair<int,int>,long double>> egdes;

  fr(i,0,N){
    fr(j,i+1,N){
      egdes.pb({{i,j},sqrtl((long double)(X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j]))-R[i]-R[j]});
    } 
  }

  fr(k,0,4){
    fr(i,0,N){
      long double dis;
      if(k == 0)
        dis = H - Y[i] - R[i];
      if(k == 2)
        dis = Y[i] - R[i];
      if(k == 1)
        dis = W - X[i] - R[i];
      if(k == 3)
        dis = X[i] - R[i];
      egdes.pb({{i,N+k},dis});
    }
  }



  sort(all(egdes),[&](auto l,auto r){
    return l.s < r.s;
  });

  vt<ar<int,3>> queries;

  fr(i,0,M){
    int r,e;
    re(r,e);
    queries.pb({r,e,i});
  }

  // trace(egdes);

  vt<string> ans(M);

  sort(all(queries));

  DSU dsu(N+4);

  int ptr = 0;

  for(auto [r,e,id] : queries){
    while(ptr < sz(egdes)){
      auto [P,D] = egdes[ptr];
      auto [i,j] = P;
      if(D < (long double)2*r){
        dsu.merge(i,j);
        // trace(i,j);
        ptr++;
      }else{
        break;
      }
    }

    auto f = [&](int u,int v) -> bool {
      return dsu.same(N+u,N+v);
    };

    ans[id].pb(e+'0');
    if(e == 1){
      // 2
      if(!(f(0,2) || f(2,3) || f(1,2)))
        ans[id].pb('2');
      // 3
      if(!(f(0,2) || f(2,3) || f(1,0) || f(1,3)))
        ans[id].pb('3');
      // 4
      if(!(f(0,3) || f(2,3) || f(1,3)))
        ans[id].pb('4');
    }else if(e == 2){
      // 1
      if(!(f(0,2) || f(2,3) || f(1,2)))
        ans[id].pb('1');
      // 3
      if(!(f(0,1) || f(2,1) || f(1,3)))
        ans[id].pb('3');
      // 4
      if(!(f(0,2) || f(1,3) || f(1,2) || f(0,3)))
        ans[id].pb('4');
    }else if(e == 3){
      // 1
      if(!(f(0,2) || f(2,3) || f(1,0) || f(1,3)))
        ans[id].pb('1');
      // 2
      if(!(f(0,1) || f(2,1) || f(1,3)))
        ans[id].pb('2');
      // 4
      if(!(f(0,1) || f(2,0) || f(0,3)))
        ans[id].pb('4');
    }else if(e == 4){
      // 1
      if(!(f(0,3) || f(2,3) || f(1,3)))
        ans[id].pb('1');
      // 2
      if(!(f(0,2) || f(1,3) || f(1,2) || f(0,3)))
        ans[id].pb('2');
      // 3
      if(!(f(0,1) || f(2,0) || f(0,3)))
        ans[id].pb('3');
    }
    sort(all(ans[id]));
  }

  for(auto i : ans)
    cout << i << "\n";





  // output_run_time();
  return 0;
}

Compilation message

park.cpp: In function 'void FUN::IO(std::string)':
park.cpp:68:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |       freopen((s+".in").c_str(),"r",stdin);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:69:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |       freopen((s+".out").c_str(),"w",stdout);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 66200 KB Output is correct
2 Correct 444 ms 66188 KB Output is correct
3 Correct 447 ms 66204 KB Output is correct
4 Correct 446 ms 66160 KB Output is correct
5 Correct 468 ms 66144 KB Output is correct
6 Correct 456 ms 66128 KB Output is correct
7 Correct 420 ms 66192 KB Output is correct
8 Correct 437 ms 66160 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 8540 KB Output is correct
2 Correct 71 ms 8536 KB Output is correct
3 Correct 58 ms 8456 KB Output is correct
4 Correct 53 ms 8556 KB Output is correct
5 Correct 57 ms 8584 KB Output is correct
6 Correct 58 ms 8620 KB Output is correct
7 Correct 50 ms 7348 KB Output is correct
8 Correct 48 ms 7412 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 66200 KB Output is correct
2 Correct 444 ms 66188 KB Output is correct
3 Correct 447 ms 66204 KB Output is correct
4 Correct 446 ms 66160 KB Output is correct
5 Correct 468 ms 66144 KB Output is correct
6 Correct 456 ms 66128 KB Output is correct
7 Correct 420 ms 66192 KB Output is correct
8 Correct 437 ms 66160 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 55 ms 8540 KB Output is correct
12 Correct 71 ms 8536 KB Output is correct
13 Correct 58 ms 8456 KB Output is correct
14 Correct 53 ms 8556 KB Output is correct
15 Correct 57 ms 8584 KB Output is correct
16 Correct 58 ms 8620 KB Output is correct
17 Correct 50 ms 7348 KB Output is correct
18 Correct 48 ms 7412 KB Output is correct
19 Correct 493 ms 73304 KB Output is correct
20 Correct 505 ms 73176 KB Output is correct
21 Correct 508 ms 73192 KB Output is correct
22 Correct 539 ms 73092 KB Output is correct
23 Correct 546 ms 73224 KB Output is correct
24 Correct 497 ms 73160 KB Output is correct