Submission #36647

#	Time	Username	Problem	Language	Result	Execution time	Memory
36647		imaxblue	Park (BOI16_park)	C++14	100 / 100	2439 ms	42448 KiB

park

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define MN 1000000007
#define fox(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define foxr(k, x) for (int k=x-1; k>=0; --k)
#define fox1r(k, x) for (int k=x; k>0; --k)
#define ms multiset
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)
#define rng() (rand() >> 3)*rand()

int n, k, w, h, N, o, R,
    x[2005], y[2005], r[2005], d[2005][4], dis[2005][2005];
int ans[4][4], D;
pq<pii> q;
void dijk(int O){
    while(!q.empty()) q.pop();
    fox(l, n){
        q.push(mp(-d[l][O], l));
        d[l][O]=(1 << 30);
    }
    while(!q.empty()){
        D=-q.top().x; N=q.top().y; q.pop();
        if (D>=d[N][O]) continue;
        d[N][O]=D;
        fox(l, n){
            if (l==N) continue;
            if (max(D, dis[N][l])<d[l][O])
                q.push(mp(-max(D, dis[N][l]), l));
        }
    }
}
int main(){
    flood(d); flood(ans);
    scanf("%i%i%i%i", &n, &k, &w, &h);
    fox(l, n){
        scanf("%i%i%i", &x[l], &y[l], &r[l]);
        d[l][0]=x[l]-r[l];
        d[l][1]=y[l]-r[l];
        d[l][2]=w-x[l]-r[l];
        d[l][3]=h-y[l]-r[l];
    }
    fox(X, n){
        fox(Y, n){
            dis[X][Y]=int(sqrt(1LL*(x[X]-x[Y])*(x[X]-x[Y])+
                     1LL*(y[X]-y[Y])*(y[X]-y[Y])))-r[X]-r[Y];
        }
    }
    fox(l, 3) dijk(l);
    fox(l, n){
        fox(l2, 3){
            fox(l4, 4)
if (l4!=l2) ans[l2][l4]=ans[l4][l2]=min(ans[l2][l4], max(d[l][l2], d[l][l2+1]));

        }
            fox(l3, 3){
                ans[l3][3]=ans[3][l3]=min(ans[3][l3], max(d[l][0], d[l][3]));
            }
            ans[0][2]=ans[2][0]=min(ans[0][2], max(d[l][0], d[l][2]));
            ans[0][3]=ans[3][0]=min(ans[0][3], max(d[l][0], d[l][2]));
            ans[1][2]=ans[1][2]=min(ans[1][2], max(d[l][0], d[l][2]));
            ans[1][3]=ans[3][1]=min(ans[1][3], max(d[l][0], d[l][2]));
            ans[0][1]=ans[1][0]=min(ans[0][1], max(d[l][1], d[l][3]));
            ans[0][2]=ans[2][0]=min(ans[0][2], max(d[l][1], d[l][3]));
            ans[2][3]=ans[3][2]=min(ans[2][3], max(d[l][1], d[l][3]));
            ans[1][3]=ans[3][1]=min(ans[1][3], max(d[l][1], d[l][3]));
    }
    /*fox(l, n){
        fox(l2, n) printf("%i ", ans[l][l2]);
        printf("\n");
    }*/
    fox(l, k){
        scanf("%i%i", &R, &o);
        --o;
        R*=2;
        fox(l, 4){
            if (R<=ans[o][l]) printf("%i", l+1);
        }
        printf("\n");
    }
    return 0;
}
/*
5 3
16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
2 2
2 1
*/

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:76:70: warning: operation on 'ans[1][2]' may be undefined [-Wsequence-point]
             ans[1][2]=ans[1][2]=min(ans[1][2], max(d[l][0], d[l][2]));
                                                                      ^
park.cpp:50:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i%i%i", &n, &k, &w, &h);
                                      ^
park.cpp:52:45: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i%i", &x[l], &y[l], &r[l]);
                                             ^
park.cpp:88:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i", &R, &o);
                              ^

• Subtask 1: 27 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42