Submission #445209

#	Time	Username	Problem	Language	Result	Execution time	Memory
445209		JovanB	Park (BOI16_park)	C++17	100 / 100	323 ms	27132 KiB

park

#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 (stderr)

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 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42