oj.uz

Submission #445209

# Submission time Handle Problem Language Result Execution time Memory
445209 2021-07-16T21:15:51 Z JovanB Park (BOI16_park) C++17
100 / 100
 323 ms 27132 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int N = 2500;

struct DSU{
    int n;
    int par[N+5];
    int sz[N+5];
    void init(int _n){
        n = _n;
        for(int i=1; i<=n; i++){
            par[i] = i;
            sz[i] = 1;
        }
    }
    int root(int x){ return (par[x] == x ? x : par[x] = root(par[x])); }
    void povezi(int a, int b){
        a = root(a);
        b = root(b);
        if(a == b) return;
        if(sz[a] < sz[b]) swap(a, b);
        sz[a] += sz[b];
        par[b] = a;
    }
    bool merged(int a, int b){ return root(a) == root(b); }
} dsu;

const int M = 100000;

bool sol[M+5][5];

int x[N+5];
int y[N+5];
int r[N+5];

struct Edge{
    int a, b, c;
    bool operator <(const Edge &x){
        return c < x.c;
    }
};

int dist(int a, int b){
    return sqrtl(1LL*(x[a]-x[b])*(x[a]-x[b]) + 1LL*(y[a]-y[b])*(y[a]-y[b]));
}

struct Query{
    int r, cr, ind;
    bool operator <(const Query &x){
        return r < x.r;
    }
} qr[M+5];

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n, m;
    cin >> n >> m;
    int w, h;
    cin >> w >> h;
    vector <Edge> edges;
    for(int i=0; i<n; i++){
        cin >> x[i] >> y[i] >> r[i];
        edges.push_back({i, n, max(0, y[i] - r[i])});
        edges.push_back({i, n+1, max(0, w - (x[i] + r[i]))});
        edges.push_back({i, n+2, max(0, h - (y[i] + r[i]))});
        edges.push_back({i, n+3, max(0, x[i] - r[i])});
    }
    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            edges.push_back({i, j, max(0, dist(i, j) - r[i] - r[j])});
        }
    }
    dsu.init(n+4);
    sort(edges.begin(), edges.end());
    int j = 0;
    for(int i=1; i<=m; i++){
        int r, b;
        cin >> r >> b;
        qr[i] = {2*r, b, i};
    }
    sort(qr+1, qr+1+m);
    for(int i=1; i<=m; i++){
        while(j < edges.size() && edges[j].c < qr[i].r){
            dsu.povezi(edges[j].a, edges[j].b);
            j++;
        }
        int x = qr[i].cr - 1;
        int ind = qr[i].ind;
        sol[ind][x] = 1;
        sol[ind][(x+1)%4] = !dsu.merged(x + n, (x+1)%4 + n) & !dsu.merged(x + n, (x+2)%4 + n) & !dsu.merged(x + n, (x+3)%4 + n);
        sol[ind][(x+2)%4] = !dsu.merged(x + n, (x+2)%4 + n) & !dsu.merged(x + n, (x+3)%4 + n) & !dsu.merged((x+1)%4 + n, (x+3)%4 + n) & !dsu.merged((x+1)%4 + n, (x+2)%4 + n);
        sol[ind][(x+3)%4] = !dsu.merged(x + n, (x+3)%4 + n) & !dsu.merged((x+3)%4 + n, (x+2)%4 + n) & !dsu.merged((x+3)%4 + n, (x+1)%4 + n);
    }
    for(int i=1; i<=m; i++){
        for(int j=1; j<=4; j++){
            if(sol[i][j-1]) cout << j;
        }
        cout << "\n";
    }
    return 0;
}

Compilation message

park.cpp: In function 'int main()':
park.cpp:90:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         while(j < edges.size() && edges[j].c < qr[i].r){
      |               ~~^~~~~~~~~~~~~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 25120 KB Output is correct
2 Correct 252 ms 25152 KB Output is correct
3 Correct 253 ms 25140 KB Output is correct
4 Correct 255 ms 25224 KB Output is correct
5 Correct 251 ms 25120 KB Output is correct
6 Correct 255 ms 25100 KB Output is correct
7 Correct 233 ms 25128 KB Output is correct
8 Correct 229 ms 25156 KB Output is correct
9 Correct 0 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 54 ms 3768 KB Output is correct
2 Correct 52 ms 3760 KB Output is correct
3 Correct 52 ms 3636 KB Output is correct
4 Correct 52 ms 3644 KB Output is correct
5 Correct 53 ms 3688 KB Output is correct
6 Correct 53 ms 3800 KB Output is correct
7 Correct 48 ms 3348 KB Output is correct
8 Correct 47 ms 3396 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 25120 KB Output is correct
2 Correct 252 ms 25152 KB Output is correct
3 Correct 253 ms 25140 KB Output is correct
4 Correct 255 ms 25224 KB Output is correct
5 Correct 251 ms 25120 KB Output is correct
6 Correct 255 ms 25100 KB Output is correct
7 Correct 233 ms 25128 KB Output is correct
8 Correct 229 ms 25156 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 54 ms 3768 KB Output is correct
12 Correct 52 ms 3760 KB Output is correct
13 Correct 52 ms 3636 KB Output is correct
14 Correct 52 ms 3644 KB Output is correct
15 Correct 53 ms 3688 KB Output is correct
16 Correct 53 ms 3800 KB Output is correct
17 Correct 48 ms 3348 KB Output is correct
18 Correct 47 ms 3396 KB Output is correct
19 Correct 300 ms 27132 KB Output is correct
20 Correct 309 ms 27128 KB Output is correct
21 Correct 307 ms 27084 KB Output is correct
22 Correct 304 ms 27024 KB Output is correct
23 Correct 323 ms 27040 KB Output is correct
24 Correct 291 ms 27128 KB Output is correct