#include<bits/stdc++.h>
/*
#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")*/
#define I inline void
#define S struct
#define vi vector<int>
#define vii vector<pair<int,int>>
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std ;
using ll = long long ;
using ld = long double ;
const int N = 5e6 + 7 , mod = 1e9 + 7 ;
const int inf = N ;
// How interesting!
int n, m;
int w, h ;
vector< pair<double,pii> > all ;
double tx[N],ty[N],tr[N] ;
int fat[N] ;
inline int find(int x){return fat[x] = (x == fat[x] ? x : find(fat[x])) ; }
inline bool same(int x, int y){return find(x) == find(y) ; }
void link(int u , int v){
u = find(u) ;
v = find(v) ;
if(u!=v)fat[u] = v ;
}
string ans[N] ;
int main(){
ios_base::sync_with_stdio(0) ;
cin.tie(0) ;
//freopen("in.in" , "r" , stdin) ;
cin >> n >> m;
cin >> w >> h ;
for(int i = 0 ;i < N ; ++ i)fat[i] = i ;
for(int i = 0 ;i < n; ++ i){
cin >> tx[i] >> ty[i] >> tr[i] ;
for(int j = 0 ;j < i ;++ j){
double d = hypot(tx[i] - tx[j] , ty[i] - ty[j]) - tr[i] - tr[j] ;
all.push_back({d , {i , j} }) ;
}
all.push_back({ty[i] - tr[i] , {i , n + 1}}) ;
all.push_back({tx[i] - tr[i] , {i , n + 2}}) ;
all.push_back({w - tx[i] - tr[i] , {i , n + 3}}) ;
all.push_back({h - ty[i] - tr[i] , {i , n + 4}}) ;
}
for(int i = 1 ;i <= m ;++ i){
double r ;
int e ;
cin >> r >> e ;
all.push_back({r * 2 , { - i , e} }) ;
}
sort(all.begin() , all.end()) ;
for(auto u : all){
if(u.second.first < 0){
// query
int j = -(u.second.first + 1) ;
int ant = u.second.second ;
if(same(n + 1 , n + 4) && same(n + 2 , n + 3) ){
ans[j] = char('0' + ant) ;
}
else if(same(n + 1, n + 4) ){
if(ant == 1 || ant == 4){
if(!same(n + 1, n + 2) && !same(n + 2, n + 4)){
ans[j] = "14" ;
}else ans[j] = char('0' + ant) ;
}else{
if(!same(n + 1, n + 3) && ! same(n + 3 , n + 4)){
ans[j] = "23" ;
}else ans[j] = char('0' + ant) ;
}
}else if(same(n + 2 , n + 3)){
if(ant == 1 || ant == 2){
if(!same(n + 1 , n + 2) && !same(n + 1 , n + 3)){
ans[j] = "12" ;
}else ans[j] = char('0' + ant) ;
}else{
if(!same(n + 2 , n + 4) && !same(n + 3, n + 4)){
ans[j] = "34" ;
}else ans[j] = char('0' + ant) ;
}
}else{
vector<int> ok(5 , 1) ;
if(same(n + 1 , n + 2))ok[1] = 0 ;
if(same(n + 1 , n + 3))ok[2] = 0 ;
if(same(n + 3 , n + 4))ok[3] = 0 ;
if(same(n + 2 , n + 4))ok[4] = 0 ;
for(int k = 1; k<= 4 ;++ k){
if((ok[ant] && ok[k]) || ant == k)
ans[j] += char('0' + k) ;
}
//ans[j] = "1234" ;
}
}else{
// update
if(u.second.second < n){
// cout<< tx[u.second.first] <<" " << ty[u.second.first] <<" "
//<< tx[u.second.second] <<" " << ty[u.second.second] <<"\n" ;
}
link(u.second.first ,u.second.second) ;
}
}
for(int i = 0 ;i < m; ++ i){
cout<< ans[i] <<"\n" ;
}
return 0 ;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
509 ms |
209472 KB |
Output is correct |
| 2 |
Correct |
500 ms |
209604 KB |
Output is correct |
| 3 |
Correct |
508 ms |
209636 KB |
Output is correct |
| 4 |
Correct |
514 ms |
209616 KB |
Output is correct |
| 5 |
Correct |
506 ms |
209600 KB |
Output is correct |
| 6 |
Correct |
510 ms |
209600 KB |
Output is correct |
| 7 |
Correct |
438 ms |
209504 KB |
Output is correct |
| 8 |
Correct |
441 ms |
209616 KB |
Output is correct |
| 9 |
Correct |
115 ms |
176504 KB |
Output is correct |
| 10 |
Correct |
116 ms |
176532 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
195 ms |
178920 KB |
Output is correct |
| 2 |
Correct |
190 ms |
179948 KB |
Output is correct |
| 3 |
Correct |
187 ms |
179816 KB |
Output is correct |
| 4 |
Correct |
187 ms |
179944 KB |
Output is correct |
| 5 |
Correct |
193 ms |
179952 KB |
Output is correct |
| 6 |
Correct |
190 ms |
179944 KB |
Output is correct |
| 7 |
Correct |
185 ms |
179824 KB |
Output is correct |
| 8 |
Correct |
188 ms |
179696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
509 ms |
209472 KB |
Output is correct |
| 2 |
Correct |
500 ms |
209604 KB |
Output is correct |
| 3 |
Correct |
508 ms |
209636 KB |
Output is correct |
| 4 |
Correct |
514 ms |
209616 KB |
Output is correct |
| 5 |
Correct |
506 ms |
209600 KB |
Output is correct |
| 6 |
Correct |
510 ms |
209600 KB |
Output is correct |
| 7 |
Correct |
438 ms |
209504 KB |
Output is correct |
| 8 |
Correct |
441 ms |
209616 KB |
Output is correct |
| 9 |
Correct |
115 ms |
176504 KB |
Output is correct |
| 10 |
Correct |
116 ms |
176532 KB |
Output is correct |
| 11 |
Correct |
195 ms |
178920 KB |
Output is correct |
| 12 |
Correct |
190 ms |
179948 KB |
Output is correct |
| 13 |
Correct |
187 ms |
179816 KB |
Output is correct |
| 14 |
Correct |
187 ms |
179944 KB |
Output is correct |
| 15 |
Correct |
193 ms |
179952 KB |
Output is correct |
| 16 |
Correct |
190 ms |
179944 KB |
Output is correct |
| 17 |
Correct |
185 ms |
179824 KB |
Output is correct |
| 18 |
Correct |
188 ms |
179696 KB |
Output is correct |
| 19 |
Correct |
592 ms |
243380 KB |
Output is correct |
| 20 |
Correct |
593 ms |
243356 KB |
Output is correct |
| 21 |
Correct |
594 ms |
243428 KB |
Output is correct |
| 22 |
Correct |
581 ms |
243360 KB |
Output is correct |
| 23 |
Correct |
586 ms |
243356 KB |
Output is correct |
| 24 |
Correct |
533 ms |
243352 KB |
Output is correct |
