Submission #568845

#TimeUsernameProblemLanguageResultExecution timeMemory
568845codebuster_10Park (BOI16_park)C++17
100 / 100
546 ms73304 KiB
#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 (stderr)

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);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...