oj.uz

Submission #258525

# Submission time Handle Problem Language Result Execution time Memory
258525 2020-08-06T05:35:19 Z 문홍윤(#5064) Park (BOI16_park) C++17
100 / 100
 729 ms 36632 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define svec(x) sort(x.begin(), x.end())
#define press(x) x.erase(unique(x.begin(), x.end()), x.end())
#define lb(x, v) lower_bound(x.begin(), x.end(), v)
#define ub(x, v) upper_bound(x.begin(), x.end(), v)
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
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+1, 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("");
    }
}
/*
5 3
16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 1
2 2
2 1
*/

Compilation message

park.cpp: In function 'int main()':
park.cpp:66:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(; pv<edg.size(); pv++){
               ~~^~~~~~~~~~~
park.cpp:39: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:41: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:59: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
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 666 ms 33468 KB Output is correct
2 Correct 663 ms 33468 KB Output is correct
3 Correct 652 ms 33468 KB Output is correct
4 Correct 669 ms 33328 KB Output is correct
5 Correct 729 ms 33340 KB Output is correct
6 Correct 702 ms 33340 KB Output is correct
7 Correct 648 ms 33396 KB Output is correct
8 Correct 627 ms 33340 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 3372 KB Output is correct
2 Correct 69 ms 3944 KB Output is correct
3 Correct 79 ms 3948 KB Output is correct
4 Correct 70 ms 4072 KB Output is correct
5 Correct 68 ms 4072 KB Output is correct
6 Correct 73 ms 4072 KB Output is correct
7 Correct 61 ms 3564 KB Output is correct
8 Correct 60 ms 3564 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 666 ms 33468 KB Output is correct
2 Correct 663 ms 33468 KB Output is correct
3 Correct 652 ms 33468 KB Output is correct
4 Correct 669 ms 33328 KB Output is correct
5 Correct 729 ms 33340 KB Output is correct
6 Correct 702 ms 33340 KB Output is correct
7 Correct 648 ms 33396 KB Output is correct
8 Correct 627 ms 33340 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 83 ms 3372 KB Output is correct
12 Correct 69 ms 3944 KB Output is correct
13 Correct 79 ms 3948 KB Output is correct
14 Correct 70 ms 4072 KB Output is correct
15 Correct 68 ms 4072 KB Output is correct
16 Correct 73 ms 4072 KB Output is correct
17 Correct 61 ms 3564 KB Output is correct
18 Correct 60 ms 3564 KB Output is correct
19 Correct 713 ms 36632 KB Output is correct
20 Correct 716 ms 36420 KB Output is correct
21 Correct 724 ms 36432 KB Output is correct
22 Correct 709 ms 36504 KB Output is correct
23 Correct 715 ms 36360 KB Output is correct
24 Correct 683 ms 36332 KB Output is correct