Submission #312976

# Submission time Handle Problem Language Result Execution time Memory
312976 2020-10-14T21:06:09 Z mohamedsobhi777 Park (BOI16_park) C++14
0 / 100
341 ms 262148 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 = 1e5 + 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){
                        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) ; 
                                continue ; 
                        }
                        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{
                                ans[j] = "1234" ;
                        }
                }else{
                        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 Runtime error 341 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 87 ms 8788 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 341 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -