Submission #313065

# Submission time Handle Problem Language Result Execution time Memory
313065 2020-10-15T06:58:07 Z mohamedsobhi777 Park (BOI16_park) C++14
100 / 100
594 ms 243428 KB
#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