oj.uz

Submission #349451

# Submission time Handle Problem Language Result Execution time Memory
349451 2021-01-17T15:48:18 Z AmirrezaM Park (BOI16_park) C++14
0 / 100
 723 ms 25172 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<pii,int> ppiii;

// vectors and Sets:
#define vc vector
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define it iterator
#define SZ(x) (ll)((x).size())
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rend(), (c).rbegin

// pairs
#define mp make_pair
#define fr first
#define sc second

// loops
#define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
#define ROF(i , n , m) for(int (i) = (n) ; (i) >= (m) ; (i)--)
//#define FOR(n) for(int (i) = (o) ; (i) < (n) ; (i)++)
//#define ROF(n) for(int (i) = (m) ; (i) >= (0) ; (i)--)

// useful numbers
#define INF ((1 << 64) - 1)
#define BPT(n) pow(2,floor(log2((n))));
#define LPT(n) pow(2,ceil(log2((n))*1.0));

// execution time check and Debug
#define StartEX; clock_t startExeTime = clock();
#define EndEX; clock_t endExeTime = clock();
#define ExTime; cerr << "\nTotal Execution Time is: " << double(-double(startExeTime)+double(endExeTime)) / CLOCKS_PER_SEC;
#define debug(x) cerr << #x << " : " << x << '\n'
#define endl "\n"

// time optimization
#define Heh ios::sync_with_stdio(false);cin.tie(0);
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O0")
#pragma GCC optimize("O1")

//Calculates b'th power of a
ll pw(int a,int b){
    ll ret = 1;
    ll mul = a;
    while(b > 0){
        if(b&1)
            ret *= mul;
        mul *= mul;
        b /= 2;
    }
    return ret;
}

//Converts s string to int
ll to_int(string s){
    ll ret = 0;
    FOR(i,0,s.size()){
        ret += pw(10,s.size()-i-1) * (ll)(s[i] - '0');
    }
    return ret;
}
const int MAXN = 2e3 + 23;
int x[MAXN] , y[MAXN] , r[MAXN] , par[MAXN] , rnk[MAXN] , n , m , h , w;
int get(int v){return par[v] = (par[v] == v ? v : get(par[v]));}
void uni(int a , int b){
    a = get(a) , b = get(b);
    if(a == b) return;
    if(rnk[a] < rnk[b]) swap(a,b);
    par[b] = a , rnk[a] += (rnk[a] == rnk[b]);
}
int main()
{
    Heh;
    cin >> n >> m >> h >> w;
    FOR(i,0,n+10) par[i] = i;
    FOR(i,0,n) cin >> x[i] >> y[i] >> r[i];
    vc<pair<int,pii> > dis;
    // n -> up , n + 1 -> right , n + 2 -> down , n+3 -> left
    FOR(i,0,n){
        dis.pb({x[i] - r[i],{i , n+3}});
        dis.pb({y[i] - r[i],{i , n+2}});
        dis.pb({h-x[i]-r[i] ,{i , n+1}});
        dis.pb({w-y[i]-r[i],{i , n}});
    }
    FOR(i,0,n-1){
        FOR(j,i+1,n){
            int dx = abs(x[i] - x[j]) , dy = abs(y[i] - y[j]);
            int d = sqrt(dx*dx*1.0 + dy*dy*1.0) - r[i] - r[j] + 1;
            dis.pb({d,{i,j}});
        }
    }
    int t[4][4];
    FOR(i,0,4)FOR(j,0,4) t[i][j] = -1;
    sort(all(dis));
    FOR(i,0,dis.size()){
        uni(dis[i].sc.sc , dis[i].sc.fr);
        int d = dis[i].fr;
        FOR(s1,0,4){
            FOR(s2,0,4){
                if(t[s1][s2] == -1){
                    if(s1 == 0 and s2 == 1){
                        if(get(n) == get(n+2) or get(n+1) == get(n+2) or get(n+2) == get(n+3)) t[s1][s2] = t[s2][s1] = d;
                    }
                    if(s1 == 3 and s2 == 2){
                        if(get(n) == get(n+2) or get(n+1) == get(n) or get(n) == get(n+3)) t[s1][s2] = t[s2][s1] = d;
                    }
                    if(s1 == 3 and s2 == 0){
                        if(get(n+3) == get(n+1) or get(n+2) == get(n+3) or get(n) == get(n+3)) t[s1][s2] = t[s2][s1] = d;
                    }
                    if(s1 == 2 and s2 == 1){
                        if(get(n+3) == get(n+1) or get(n+2) == get(n+1) or get(n) == get(n+1)) t[s1][s2] = t[s2][s1] = d;
                    }
                    if(s1 == 2 and s2 == 0){
                        if(get(n) == get(n+2) or get(n+3) == get(n+1) or get(n) == get(n+1) or get(n+3) == get(n+2)) t[s1][s2] = t[s2][s1] = d;
                    }
                    if(s1 == 3 and s2 == 1){
                        if(get(n) == get(n+2) or get(n+3) == get(n+1) or get(n) == get(n+3) or get(n+1) == get(n+2)) t[s1][s2] = t[s2][s1] = d;
                    }
                }
            }
        }
    }
    while(m--){
        int st , r;
        cin >> r >> st;
        st-- , r *= 2;
        FOR(i,0,4){
            if(i == st or t[st][i] == -1 or t[st][i] > r) cout << i+1;
        }
        cout << endl;
    }
    // Doesn't Ac? Read the Bottom :/
}

// stuff you should look for(Thanks Benq)
//	*** int overflow, array bounds
//	* special cases (n=1?)
//	**** do smth instead of nothing and stay organized
//	* WRITE STUFF DOWN
//	*** DON'T GET STUCK ON ONE APPROACH

Compilation message

park.cpp:37:9: warning: ISO C++11 requires whitespace after the macro name
   37 | #define StartEX; clock_t startExeTime = clock();
      |         ^~~~~~~
park.cpp:38:9: warning: ISO C++11 requires whitespace after the macro name
   38 | #define EndEX; clock_t endExeTime = clock();
      |         ^~~~~
park.cpp:39:9: warning: ISO C++11 requires whitespace after the macro name
   39 | #define ExTime; cerr << "\nTotal Execution Time is: " << double(-double(startExeTime)+double(endExeTime)) / CLOCKS_PER_SEC;
      |         ^~~~~~
park.cpp: In function 'll to_int(std::string)':
park.cpp:26:32: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                ^
park.cpp:66:5: note: in expansion of macro 'FOR'
   66 |     FOR(i,0,s.size()){
      |     ^~~
park.cpp:26:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                            ~~~~^~~~~
park.cpp:66:5: note: in expansion of macro 'FOR'
   66 |     FOR(i,0,s.size()){
      |     ^~~
park.cpp: In function 'int main()':
park.cpp:26:32: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                ^
park.cpp:84:5: note: in expansion of macro 'FOR'
   84 |     FOR(i,0,n+10) par[i] = i;
      |     ^~~
park.cpp:26:32: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                ^
park.cpp:85:5: note: in expansion of macro 'FOR'
   85 |     FOR(i,0,n) cin >> x[i] >> y[i] >> r[i];
      |     ^~~
park.cpp:26:32: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                ^
park.cpp:88:5: note: in expansion of macro 'FOR'
   88 |     FOR(i,0,n){
      |     ^~~
park.cpp:26:32: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                ^
park.cpp:94:5: note: in expansion of macro 'FOR'
   94 |     FOR(i,0,n-1){
      |     ^~~
park.cpp:26:32: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                ^
park.cpp:95:9: note: in expansion of macro 'FOR'
   95 |         FOR(j,i+1,n){
      |         ^~~
park.cpp:26:32: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                ^
park.cpp:102:5: note: in expansion of macro 'FOR'
  102 |     FOR(i,0,4)FOR(j,0,4) t[i][j] = -1;
      |     ^~~
park.cpp:26:32: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                ^
park.cpp:102:15: note: in expansion of macro 'FOR'
  102 |     FOR(i,0,4)FOR(j,0,4) t[i][j] = -1;
      |               ^~~
park.cpp:26:32: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                ^
park.cpp:104:5: note: in expansion of macro 'FOR'
  104 |     FOR(i,0,dis.size()){
      |     ^~~
park.cpp:26:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                            ~~~~^~~~~
park.cpp:104:5: note: in expansion of macro 'FOR'
  104 |     FOR(i,0,dis.size()){
      |     ^~~
park.cpp:26:32: warning: unnecessary parentheses in declaration of 's1' [-Wparentheses]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                ^
park.cpp:107:9: note: in expansion of macro 'FOR'
  107 |         FOR(s1,0,4){
      |         ^~~
park.cpp:26:32: warning: unnecessary parentheses in declaration of 's2' [-Wparentheses]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                ^
park.cpp:108:13: note: in expansion of macro 'FOR'
  108 |             FOR(s2,0,4){
      |             ^~~
park.cpp:26:32: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define FOR(i , m , n) for(int (i) = (m) ; (i) < (n) ; (i)++)
      |                                ^
park.cpp:136:9: note: in expansion of macro 'FOR'
  136 |         FOR(i,0,4){
      |         ^~~

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 723 ms 25172 KB Output is correct
2 Incorrect 713 ms 25164 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 1128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 723 ms 25172 KB Output is correct
2 Incorrect 713 ms 25164 KB Output isn't correct
3 Halted 0 ms 0 KB -