oj.uz

Submission #485796

# Submission time Handle Problem Language Result Execution time Memory
485796 2021-11-09T11:53:15 Z radal Park (BOI16_park) C++14
100 / 100
 451 ms 67380 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O2")
#pragma GCC target("avx2,fma")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<long double,long double> pld;
const long long int N = 2e3+10,mod = 1e9+7,inf = 1e9,sq = 500,maxm = 1e5+10;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
inline int poww(int n,ll k){
    int c = 1;
    while (k){
        if (k&1) c = (1ll*c*n)%mod;
        n = (1ll*n*n)%mod;
        k >>= 1;
    }
    return c;
}
vector<pair<long double,pll> > e;
pair<pll,int> point[N];
int par[N];
inline ld dist(pll a,pll b){
    return sqrt(ld((a.X-b.X)*(a.X-b.X)+(a.Y-b.Y)*(a.Y-b.Y)));
}
inline ld dist(pair<pll,int> p1,pair<pll,int> p2){
    return dist(p1.X,p2.X)-p1.Y-p2.Y;
}
int getpar(int v){
    if (par[v] == v) return v;
    return par[v] = getpar(par[v]);
}
inline void mg(int u,int v){
    u = getpar(u);
    v = getpar(v);
    par[u] = v;
    return;
}
pair<pll,int> a[maxm];
bool ans[maxm][4];
int main(){
    ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n,m,w,h;
    cin >> n >> m >> w >> h;
    e.reserve(n*n+6*n);
    rep(i,1,n+1){
        par[i] = i;
        cin >> point[i].X.X >> point[i].X.Y >> point[i].Y;
        rep(j,1,i){
            e.pb({dist(point[i],point[j]),{i,j}});
        }
    }
    rep(i,1,5) par[n+i] = n+i;
    rep(i,1,n+1){
        int x = point[i].X.X,y = point[i].X.Y,r = point[i].Y;
        e.pb({y-r,{n+1,i}});
        e.pb({x-r,{n+4,i}});
        e.pb({w-x-r,{n+2,i}});
        e.pb({h-y-r,{n+3,i}});
    }
    rep(i,0,m){
        cin >> a[i].X.X >> a[i].X.Y;
        a[i].Y = i;
        a[i].X.X *= 2;
        a[i].X.Y--;
    }
    sort(e.begin(),e.end());
    sort(a,a+m);
    int l = -1;
    int sz = e.size();
    rep(i,0,m){
        while (l < sz-1 && e[l+1].X < a[i].X.X){
            l++;
            mg(e[l].Y.X,e[l].Y.Y);
        }
        int st = a[i].X.Y,ind = a[i].Y;
        ans[ind][st] = 1;
        int u1=  getpar(n+1),u2 = getpar(n+2),u3 = getpar(n+3),u4 = getpar(n+4);
        if (st == 0){
            if (u1 != u2 && u1 != u3 && u1 != u4) ans[ind][1] = 1;
            if (u1 != u3 && u2 != u4 && u1 != u4 && u2 != u3) ans[ind][2] = 1;
            if (u4 != u2 && u4 != u3 && u1 != u4) ans[ind][3] = 1;
        }
        if (st == 1){
            if (u1 != u2 && u1 != u3 && u1 != u4) ans[ind][0] = 1;
            if (u1 != u2 && u2 != u4 && u2 != u3) ans[ind][2] = 1;
            if (u4 != u2 && u4 != u3 && u1 != u2 && u1 != u3) ans[ind][3] = 1;
        }
        if (st == 2){
            if (u1 != u2 && u2 != u3 && u2 != u4) ans[ind][1] = 1;
            if (u1 != u3 && u2 != u4 && u1 != u4 && u2 != u3) ans[ind][0] = 1;
            if (u3 != u2 && u4 != u3 && u1 != u3) ans[ind][3] = 1;
        }
        if (st == 3){
            if (u4 != u2 && u4 != u3 && u1 != u4) ans[ind][0] = 1;
            if (u1 != u3 && u2 != u4 && u1 != u2 && u4 != u3) ans[ind][1] = 1;
            if (u3 != u2 && u4 != u3 && u3 != u4) ans[ind][2] = 1;
        }
    }
    rep(i,0,m){
        rep(j,0,4) if (ans[i][j]) cout << j+1;
        cout << endl;
    }
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 63172 KB Output is correct
2 Correct 391 ms 63160 KB Output is correct
3 Correct 383 ms 63172 KB Output is correct
4 Correct 423 ms 63168 KB Output is correct
5 Correct 390 ms 63172 KB Output is correct
6 Correct 381 ms 63172 KB Output is correct
7 Correct 366 ms 63216 KB Output is correct
8 Correct 357 ms 63248 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 5140 KB Output is correct
2 Correct 43 ms 5060 KB Output is correct
3 Correct 42 ms 4984 KB Output is correct
4 Correct 40 ms 5040 KB Output is correct
5 Correct 41 ms 5012 KB Output is correct
6 Correct 42 ms 5156 KB Output is correct
7 Correct 38 ms 4492 KB Output is correct
8 Correct 40 ms 4532 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 63172 KB Output is correct
2 Correct 391 ms 63160 KB Output is correct
3 Correct 383 ms 63172 KB Output is correct
4 Correct 423 ms 63168 KB Output is correct
5 Correct 390 ms 63172 KB Output is correct
6 Correct 381 ms 63172 KB Output is correct
7 Correct 366 ms 63216 KB Output is correct
8 Correct 357 ms 63248 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 43 ms 5140 KB Output is correct
12 Correct 43 ms 5060 KB Output is correct
13 Correct 42 ms 4984 KB Output is correct
14 Correct 40 ms 5040 KB Output is correct
15 Correct 41 ms 5012 KB Output is correct
16 Correct 42 ms 5156 KB Output is correct
17 Correct 38 ms 4492 KB Output is correct
18 Correct 40 ms 4532 KB Output is correct
19 Correct 431 ms 67352 KB Output is correct
20 Correct 420 ms 67232 KB Output is correct
21 Correct 451 ms 67356 KB Output is correct
22 Correct 427 ms 67268 KB Output is correct
23 Correct 419 ms 67224 KB Output is correct
24 Correct 413 ms 67380 KB Output is correct