oj.uz

Submission #258537

# Submission time Handle Problem Language Result Execution time Memory
258537 2020-08-06T05:50:31 Z 문홍윤(#5064) Park (BOI16_park) C++17
0 / 100
 661 ms 33556 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define svec(x) sort(x.begin(), x.end())
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const LL llinf=1500000000;

int n, m;
LL r[2010], w, h;
pll p[2010];
vector<pair<LL, pii> > edg;
vector<pair<pii, int> > query;
int ans[100010];

struct UNION_FIND{
    int par[2010];
    UNION_FIND(){for(int i=1; i<=2005; i++)par[i]=i;}
    int findpar(int num){return num==par[num]?num:par[num]=findpar(par[num]);}
    void mergepar(int a, int b){par[findpar(a)]=findpar(b);}
}uf;

void upd(int num, int a){
    int tmp=15-(1<<a);
    ans[num]&=tmp;
}

int main(){
    scanf("%d %d %lld %lld", &n, &m, &w, &h);
    for(int i=4; i<=n+3; i++){
        scanf("%lld %lld %lld", &p[i].F, &p[i].S, &r[i]);
        for(int j=4; j<i; j++){
            LL l=1, rr=llinf;
            LL d=(p[i].F-p[j].F)*(p[i].F-p[j].F)+(p[i].S-p[j].S)*(p[i].S-p[j].S);
            while(l<rr){
                LL mid=(l+rr)/2+1;
                if((r[i]+r[j]+mid)*(r[i]+r[j]+mid)>d)rr=mid-1;
                else l=mid;
            }
            edg.eb(l, mp(i, j));
        }
        edg.eb(p[i].S-r[i]+1, mp(0, i));
        edg.eb(w-p[i].F-r[i]+1, mp(1, i));
        edg.eb(h-p[i].S-r[i]+1, mp(2, i));
        edg.eb(p[i].F-r[i]+1, mp(3, i));
    }
    for(int i=1; i<=m; i++){
        int a; LL b;
        scanf("%lld %d", &b, &a);
        query.eb(mp(b*2, a-1), i);
        ans[i]=15;
    }
    svec(edg); svec(query);
    int pv=0;
    for(auto j:query){
        for(; pv<edg.size(); pv++){
            if(edg[pv].F>j.F.F)break;
            uf.mergepar(edg[pv].S.F, edg[pv].S.S);
        }
        if(uf.findpar((0+j.F.S)%4)==uf.findpar((1+j.F.S)%4))upd(j.S, (1+j.F.S)%4);
        if(uf.findpar((0+j.F.S)%4)==uf.findpar((2+j.F.S)%4))upd(j.S, (1+j.F.S)%4);
        if(uf.findpar((0+j.F.S)%4)==uf.findpar((3+j.F.S)%4))upd(j.S, (1+j.F.S)%4);
        if(uf.findpar((0+j.F.S)%4)==uf.findpar((2+j.F.S)%4))upd(j.S, (2+j.F.S)%4);
        if(uf.findpar((0+j.F.S)%4)==uf.findpar((3+j.F.S)%4))upd(j.S, (2+j.F.S)%4);
        if(uf.findpar((1+j.F.S)%4)==uf.findpar((2+j.F.S)%4))upd(j.S, (2+j.F.S)%4);
        if(uf.findpar((1+j.F.S)%4)==uf.findpar((3+j.F.S)%4))upd(j.S, (2+j.F.S)%4);
        if(uf.findpar((3+j.F.S)%4)==uf.findpar((0+j.F.S)%4))upd(j.S, (3+j.F.S)%4);
        if(uf.findpar((3+j.F.S)%4)==uf.findpar((1+j.F.S)%4))upd(j.S, (3+j.F.S)%4);
        if(uf.findpar((3+j.F.S)%4)==uf.findpar((2+j.F.S)%4))upd(j.S, (3+j.F.S)%4);
    }
    for(int i=1; i<=m; i++){
        for(int j=1; j<=4; j++){
            if(ans[i]&(1<<(j-1)))printf("%d", j);
        }
        puts("");
    }
}

Compilation message

park.cpp: In function 'int main()':
park.cpp:60:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(; pv<edg.size(); pv++){
               ~~^~~~~~~~~~~
park.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %lld %lld", &n, &m, &w, &h);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld %lld", &p[i].F, &p[i].S, &r[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %d", &b, &a);
         ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 643 ms 33344 KB Output is correct
2 Correct 661 ms 33340 KB Output is correct
3 Correct 654 ms 33396 KB Output is correct
4 Correct 644 ms 33368 KB Output is correct
5 Correct 642 ms 33556 KB Output is correct
6 Correct 649 ms 33528 KB Output is correct
7 Correct 595 ms 33340 KB Output is correct
8 Incorrect 579 ms 33340 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 3048 KB Output is correct
2 Incorrect 68 ms 2920 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 643 ms 33344 KB Output is correct
2 Correct 661 ms 33340 KB Output is correct
3 Correct 654 ms 33396 KB Output is correct
4 Correct 644 ms 33368 KB Output is correct
5 Correct 642 ms 33556 KB Output is correct
6 Correct 649 ms 33528 KB Output is correct
7 Correct 595 ms 33340 KB Output is correct
8 Incorrect 579 ms 33340 KB Output isn't correct
9 Halted 0 ms 0 KB -