제출 #274885

#제출 시각아이디문제언어결과실행 시간메모리
274885rqiPark (BOI16_park)C++14
100 / 100
540 ms35672 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef pair<int, int> pi; typedef long double ld; #define mp make_pair #define f first #define s second #define pb push_back #define all(x) begin(x), end(x) const int MOD = 1000000007; const int mx = 100005; int n, m; ll w, h; ll k; ll x[mx]; ll y[mx]; ll r[mx]; ll R[mx]; int e[mx]; pair<vi, vi> sep[7]; pi connec[7]; int his[7]; //lowest value to make it connected int E[mx]; void init(){ for(int i = 1; i <= n+4; i++){ E[i] = -1; } } int get(int a){ if(E[a] < 0) return a; E[a] = get(E[a]); return E[a]; } void unite(int a, int b){ a = get(a); b = get(b); if(a == b) return; if(-E[a] < -E[b]) swap(a, b); E[a]+=E[b]; E[b] = a; } // int comp[mx]; // vi adj[mx]; // void ae(int a, int b){ // adj[a].pb(b); adj[b].pb(a); // } // void dfs(int node, int val){ // if(comp[node] != 0) return; // comp[node] = val; // for(auto u: adj[node]){ // dfs(u, val); // } // } // bool works(int ind, ll mid){ // for(int i = 1; i <= n+4; i++){ // comp[i] = 0; // adj[i].clear(); // } // //add all the edges // for(int i = 1; i <= n; i++){ // for(int j = i+1; j <= n; j++){ // if((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]) < (r[i]+r[j]+2*mid)*(r[i]+r[j]+2*mid)){ // ae(i, j); // } // } // } // for(int i = 1; i <= n; i++){ // ll xlo = x[i]-r[i]-2*mid; // ll xhi = x[i]+r[i]+2*mid; // ll ylo = y[i]-r[i]-2*mid; // ll yhi = y[i]+r[i]+2*mid; // if(xlo < 0){ // ae(i, n+4); // } // if(xhi > w){ // ae(i, n+2); // } // if(ylo < 0){ // ae(i, n+1); // } // if(yhi > h){ // ae(i, n+3); // } // } // for(int i = 1; i <= n+4; i++){ // if(comp[i] != 0) continue; // dfs(i, i); //node, val // } // if(comp[connec[ind].f] == comp[connec[ind].s]) return 1; // return 0; // } // void findHis(){ // for(int i = 1; i <= 6; i++){ // ll lo = 0; // ll hi = MOD; // while(lo < hi){ // ll mid = (lo+hi)/2; // if(works(i, mid)){ // hi = mid; // } // else lo = mid+1; // } // his[i] = lo; // } // } ll getSqrt(ll dist2, ll sum){ if(dist2 == sum*sum) return 1; ld dist = sqrt(ld(dist2)); dist-=ld(sum); dist/=ld(2); ll res = round(dist); while(res >= 1 && dist2 < (sum+2*(res-1))*(sum+2*(res-1))){ res--; } while(dist2 >= (sum+2*res)*(sum+2*res)){ res++; } return res; } void findHis(){ vector<pair<ll, pi>> eds; for(int i = 1; i <= n; i++){ for(int j = i+1; j <= n; j++){ eds.pb(mp(getSqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]), r[i]+r[j]), mp(i, j))); } } for(int i = 1; i <= n; i++){ ll xlo = x[i]-r[i]; ll xhi = x[i]+r[i]; ll ylo = y[i]-r[i]; ll yhi = y[i]+r[i]; eds.pb(mp((xlo-0)/2+1, mp(i, n+4))); eds.pb(mp((w-xhi)/2+1, mp(i, n+2))); eds.pb(mp((ylo-0)/2+1, mp(i, n+1))); eds.pb(mp((h-yhi)/2+1, mp(i, n+3))); } sort(all(eds)); for(auto u: eds){ unite(u.s.f, u.s.s); //cout << u.f << " " << u.s.f << " " << u.s.s << "\n"; vi comps(5, 0); // for(int i = 1; i <= n+4; i++){ // cout << i << " " << E[i] << "\n"; // } for(int j = 1; j <= 4; j++){ comps[j] = get(n+j); //cout << j << " " << comps[j] << "\n"; } for(int j = 1; j <= 6; j++){ //cout << "HIS " << j << " " << his[j] << "\n"; if(his[j] != -1) continue; if(comps[connec[j].f-n] == comps[connec[j].s-n]){ his[j] = u.f; //cout << "HIS " << j << " " << his[j] << "\n"; } } } } int main(){ cin.tie(0)->sync_with_stdio(0); cin >> n >> m; cin >> w >> h; init(); for(int i = 1; i <= 6; i++){ his[i] = -1; } sep[1] = mp(vi{1}, vi{2, 3, 4}); sep[2] = mp(vi{2}, vi{1, 3, 4}); sep[3] = mp(vi{3}, vi{1, 2, 4}); sep[4] = mp(vi{4}, vi{1, 2, 3}); sep[5] = mp(vi{1, 4}, vi{2, 3}); sep[6] = mp(vi{1, 2}, vi{3, 4}); connec[1] = mp(n+1, n+4); connec[2] = mp(n+1, n+2); connec[3] = mp(n+2, n+3); connec[4] = mp(n+3, n+4); connec[5] = mp(n+1, n+3); connec[6] = mp(n+2, n+4); for(int i = 1; i <= n; i++){ cin >> x[i] >> y[i] >> r[i]; } for(int i = 1; i <= m; i++){ cin >> R[i] >> e[i]; k = max(k, r[i]); } findHis(); for(int i = 1; i <= m; i++){ vector<bool> v(5, true); for(int j = 1; j <= 6; j++){ if(R[i] >= his[j]){ for(auto u: sep[j].f){ if(u == e[i]){ for(auto z: sep[j].s){ v[z] = false; } } } for(auto u: sep[j].s){ if(u == e[i]){ for(auto z: sep[j].f){ v[z] = false; } } } } } for(int j = 1; j <= 4; j++){ if(v[j] == true) cout << j; } cout << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...