이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |